P2150 [NOI2015] 寿司晚宴
Statement
给定 \(n-1\) 个数分别为 \(2\sim n\)，从中选出交集为空的两个集合 \(A,B\)（集合的并集不必须为 \(\{2,\dots,n\}\)，且集合可为空）使得不存在 \(a\in A,b\in B\) 满足 \((a,b)\ne 1\)（即任意两个数均互质），将方案数对 \(p\) 取模后输出。
\(2\le n\le 500\)，\(0\le p\le 10^9\)
Solution
Subtask 1 (30 pts)
不存在 \(a\in A,b\in B\) 满足 \((a,b)\ne 1\) 等价于 \(A\) 集合所有数的质因子构成的集合与 \(B\) 集合所有数的质因子构成的集合交集为空（重点）。
那么，不难想到维护质因子构成的集合，而 \(30\) 以内至多有 \(10\) 个质数，故仅需对于每一个集合用 \(2^{10}\) 的整数存储即可。转移如下：
\[\begin{cases} &f_{i,j\cup mask_i,k}=f_{i,j\cup mask_i,k}+f_{i-1,j,k} &k\cap(j\cup mask_i)=0\\ &f_{i,j,k\cup mask_i}=f_{i,j,k\cup mask_i}+f_{i-1,j,k} &(k\cup mask_i)\cap j=0\\ \end{cases} \]解释：\(f_{i,j,k}\) 表示前 \(i\) 个数，\(A\) 集合为 \(j\)，\(B\) 集合为 \(k\) 的方案数。转移枚举当前数填至 \(A\) 或 \(B\) 集合即可，注意需要判断填完后是否满足条件。\(mask_i\) 表示 \(i\) 的质因子构成的集合。
//给出转移的核心代码
f[1][0][0] = 1;
for (int k = 2; k <= n; k ++)
for (int i = 0; i < 1 << cnt; i ++)
for (int j = 0; j < 1 << cnt; j ++) {
f[k][i][j] = (f[k][i][j] + f[k - 1][i][j]) % p;
if (((i | mask[k]) & j) == 0) f[k][i | mask[k]][j] = (f[k][i | mask[k]][j] + f[k - 1][i][j]) % p;
if ((i & (j | mask[k])) == 0) f[k][i][j | mask[k]] = (f[k][i][j | mask[k]] + f[k - 1][i][j]) % p;
}
Subtask 2 (100 pts)
大于 \(\sqrt n\) 的质因子有且仅有 \(1\) 个
证明：若存在 \(2\) 个大于 \(\sqrt n\) 的质因子，则相乘必然大于 \(n\)，与假设矛盾，证毕。
而当 \(n=500\) 时，\(\le \sqrt n\) 的质数仅有 \(8\) 个，所以可以状压 \(\le \sqrt n\) 的质因子。对于 \(>\sqrt n\) 的质因子，只需要特殊地判断位于哪一个集合即可。
具体来说，将所有数按 \(>\sqrt n\) 的质因子从小到大排序。对于所有 \(>\sqrt n\) 质因子相同的数，只需要统一计算即可。令 \(f_{i,j,k}\) 表示前 \(i\) 个数，\(A\) 集合为 \(j\)，\(B\) 集合为 \(k\)，且当前质因子填在 \(A\) 集合的方案数；\(g_{i,j,k}\) 表示 \(A\) 集合为 \(j\)，\(B\) 集合为 \(k\)，且当前质因子填在 \(B\) 集合的方案数，则有转移：
\[\begin{cases} & f_{i,j\cup mask_i,k}=f_{i,j\cup mask_i,k}+f_{i-1,j,k}\\ & g_{i,j,k\cup mask_i}=g_{i,j,k\cup mask_i}+g_{i-1,j,k}\\ \end{cases} \]与上文转移类似，这里不多做赘述。
那么，对于每一次统一计算，前面的数但是可以随便填的，所以 \(f,g\) 初始均为 \(dp_{i,j,k}\)（记录着最终的答案）。统一计算完后，再更新 \(dp\) 即可。
\[\begin{aligned} dp_{i,j,k}=f_{i,j,k}+g_{i,j,k}-dp_{i-1,j,k} \end{aligned} \]最后减去 \(dp_{i-1,j,k}\) 的原因是，如果 \(A,B\) 集合对于蕴含当前质因子的所有数均未选择，则 \(dp_{i-1,j,k}\) 则会加入贡献 \(2\) 次，所以需要减去 \(1\) 次。
时间复杂度：\(O(4^{\pi(\sqrt n)}n)\)；或优化至 \(O(3^{\pi(\sqrt n)}n)\)
\(\pi(n)\) 表示小于等于 \(n\) 的质数个数，在本题中 \(\pi(\sqrt n)\) 最大为 \(8\)。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 5e2 + 10, M = 1 << 8;
int n, p;
int lgt[N], id[20] = {0, 0, 0, 1, 0, 2, 0, 3, 0, 0, 0, 4, 0, 5, 0, 0, 0, 6, 0, 7};
int dp[M][M], f[M][M], g[M][M], mask[N];
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> p;
std::vector<int> num;
const int B = sqrt(n) + 1;
for (int i = 2; i <= n; i ++) {
int tmp = i;
for (int j = 2; j <= tmp / j; j ++) if (tmp % j == 0) while (tmp % j == 0) tmp /= j, mask[i] |= 1 << id[j];
if (tmp >= B) lgt[i] = tmp;
else if (tmp > 1) mask[i] |= 1 << id[tmp];
num.emplace_back(i);
}
sort(num.begin(), num.end(), [&](int a, int b) {
if (lgt[a] == lgt[b]) return a < b;
return lgt[a] < lgt[b];
});
dp[0][0] = 1;
for (int k = 0; k < num.size(); k ++) {
if (!k || !lgt[num[k]] || lgt[num[k]] != lgt[num[k - 1]]) memcpy(f, dp, sizeof dp), memcpy(g, dp, sizeof dp);
for (int i = M - 1; i >= 0; i --)
for (int j = M - 1; j >= 0; j --) {
if (((i | mask[num[k]]) & j) == 0) f[i | mask[num[k]]][j] = (f[i | mask[num[k]]][j] + f[i][j]) % p;
if ((i & (j | mask[num[k]])) == 0) g[i][j | mask[num[k]]] = (g[i][j | mask[num[k]]] + g[i][j]) % p;
}
if (k + 1 == num.size() || !lgt[num[k]] || lgt[num[k + 1]] != lgt[num[k]])
for (int i = 0; i < M; i ++)
for (int j = 0; j < M; j ++)
dp[i][j] = (f[i][j] + g[i][j] - dp[i][j] + p) % p;
}
int res = 0;
for (int i = 0; i < M; i ++)
for (int j = 0; j < M; j ++)
res = (res + dp[i][j]) % p;
cout << res << endl;
return 0;
}