根号分治

根号分治，是暴力美学的集大成体现。

与其说是一种算法，我们不如称它为一个常用的trick。

根号分治，其实就是将一个数据较大、复杂度较大的解法转化为根号级别的解法

寿司晚宴

题目

题目链接：P2150 [NOI2015] 寿司晚宴

[NOI2015] 寿司晚宴

题目描述

为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。

在晚宴上，主办方为大家提供了 $n−1$ 种不同的寿司，编号 $1,2,3,\ldots,n-1$，其中第 $i$ 种寿司的美味度为 $i+1$。（即寿司的美味度为从 $2$ 到 $n$）

现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 $x$ 的寿司，小 W 品尝的寿司中存在一种美味度为 $y$ 的寿司，而 $x$ 与 $y$ 不互质。

现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 $p$ 取模）。注意一个人可以不吃任何寿司。

输入格式

输入文件的第 $1$ 行包含 $2$ 个正整数 $n, p$ 中间用单个空格隔开，表示共有 $n$ 种寿司，最终和谐的方案数要对 $p$ 取模。

输出格式

输出一行包含 $1$ 个整数，表示所求的方案模 $p$ 的结果。

提示

【数据范围】

勘误：$0 < p \le 10^9 $

思路

首先，要让两个人选的数字全部互质，那么有一个显然的充要条件：甲选的数字的质因数集合和乙选的数字的质因数集合没有交集

假如有状压基础的话，不难发现这道题在n较小的情况下可以开个状压搞搞：

把质数从小到大排列成一行，0和1分别表示是否存在该质因数，能够表示一种状态$S$

那么可以找到状态转移方程：·

当遍历到第 i 个数的时候

读于甲乙所有可能集合的状态存在

$if \space S_乙\&S_i==0 \space\space dp[i][S_甲|S_i][S_乙]+=dp[i][S_甲][S_乙]$

$if \space S_甲\&S_i==0 \space\space dp[i][S_甲][S_乙|S_i]+=dp[i][S_甲][S_乙]$

稍微优化成二维dp：

因为按位或运算是越算越大的，所以我们可以把甲乙集合的状态从大往小遍历，这样每次更新只是覆盖遍历过的

$if \space S_乙\&S_i==0 \space\space dp[S_甲|S_i][S_乙]+=dp[S_甲][S_乙]$

$if \space S_甲\&S_i==0 \space\space dp[S_甲][S_乙|S_i]+=dp[S_甲][S_乙]$

状压dp的思路到这里就到头了，唯一的问题是当n=500时，有95个可能可能的质因数，对应着$2^{95}$个状态，这显然不现实。

可以证明：对于每一个$n$，大于等于$\sqrt{n}$的质因数个数最多只有一个

也就是说一个小于500的数，最多只可能有1个比22大的质因子

所以说我们可以按照大于大于等于$\sqrt{n}$的质因数，将所有寿司分组，每组放在一起dp，这样只需要表示$\sqrt{n}$以内的质因数和组内唯一一个大于等于$\sqrt{n}$的质因数的状态就好了，遍历到下一组时，需要将大质数那一位的状态更新，（即将上一组存在大质因数的状态加到无大质因数的状态中，然后清零，毕竟后面的组都涉及不到那个大质因数了）。

总时间复杂度为$O(n2^{16})$

代码：

// 洛谷 P2150 [NOI2015] 寿司晚宴
// 状压dp+根号优化
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define pb emplace_back
const int N = 513, INF = 1e9, mod = 998244353;
ll n, p, sieve[N], state[N], dp[N][N], ans;
vector<int> prime_small, prime_big;
int main()
{
    cin >> n >> p;

    // 筛 获得n以内的质数
    for (int i = 2; i <= n; i++)
        for (int j = 2; j * i <= n; j++)
            sieve[i * j] = 1;
    for (int i = 2; i <= n; i++)
        if (sieve[i] == 0)
        {
            if (i * i < n)
                prime_small.pb(i);
            else
                prime_big.pb(i);
        }

    // 筛筛 获得2-n的每个数的状态
    for (int i = 0; i < prime_small.size(); i++)
        for (int j = 1; j * prime_small[i] <= n; j++)
            state[j * prime_small[i]] |= (1 << i);
    for (int i = 0; i < prime_big.size(); i++)
        for (int j = 1; j * prime_big[i] <= n; j++)
            state[j * prime_big[i]] |= (1 << prime_small.size());

    // 状压dp
    dp[0][0] = 1;//甲乙开始都为空集的状态数为1
    // 分组dp有大质数的
    for (int i = 0; i < prime_big.size(); i++)
    {
        for (int j = 1; j * prime_big[i] <= n; j++)//根据每个大质因数分别dp
        {
            int s = state[j * prime_big[i]];
            for (int x = (1 << (prime_small.size() + 1)) - 1; x >= 0; x--)
                for (int y = (1 << (prime_small.size() + 1)) - 1; y >= 0; y--)
                {
                    if ((s & y) == 0)
                        dp[x | s][y] = (dp[x | s][y] + dp[x][y]) % p;
                    if ((s & x) == 0)
                        dp[x][y | s] = (dp[x][y | s] + dp[x][y]) % p;
                }
        }
        //将大质数那一位的状态更新
        for (int x = (1 << (prime_small.size())) - 1; x >= 0; x--)
            for (int y = (1 << (prime_small.size())) - 1; y >= 0; y--)
            {
                dp[x][y] = (dp[x][y] + (dp[x + (1 << prime_small.size())][y] + dp[x][y + (1 << prime_small.size())]) % p) % p;
                dp[x + (1 << prime_small.size())][y] = dp[x][y + (1 << prime_small.size())] = 0;
            }
    }
    // dp没大质数的
    for (int i = 2; i <= n; i++)
        if ((state[i] >> prime_small.size()) == 0)
        {
            int s = state[i];
            for (int x = (1 << (prime_small.size())) - 1; x >= 0; x--)
                for (int y = (1 << (prime_small.size())) - 1; y >= 0; y--)
                {
                    if ((s & y) == 0)
                        dp[x | s][y] = (dp[x | s][y] + dp[x][y]) % p;
                    if ((s & x) == 0)
                        dp[x][y | s] = (dp[x][y | s] + dp[x][y]) % p;
                }
        }

    //计算答案
    for (int x = (1 << (prime_small.size())) - 1; x >= 0; x--)
        for (int y = (1 << (prime_small.size())) - 1; y >= 0; y--)
            ans = (ans + dp[x][y]) % p;

    cout << ans << endl;
    return 0;
}

• 本文作者： NICK
• 本文链接： https://nicccce.github.io/ACM/Root-Divide/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！