题面
Description
为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。
在晚宴上,主办方为大家提供了 n−1 种不同的寿司，编号 1,2,3,…,n−1，其中第 i 种寿司的美味度为 i+1 （即寿司的美味度为从 2 到 n）。
现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 x 的寿司，小 W 品尝的寿司中存在一种美味度为 y 的寿司，而 x 与 y 不互质。
现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 p 取模）。注意一个人可以不吃任何寿司。
Input
输入文件的第 1 行包含 2 个正整数 n,p，中间用单个空格隔开，表示共有 n 种寿司，最终和谐的方案数要对 p 取模。
Output
输出一行包含 1 个整数，表示所求的方案模 p 的结果。
Samples
input:
3 10000
Sample Output
9
HINT
\(2≤n≤500\)
\(0<p≤1000000000\)
Solution
考虑\(n\)比较小的情况: 我们用f[i][j][k]表示到第\(i\)个数, 其中两个取的质因子情况分别为\(j\)和\(k\)的方案数, 01背包去掉第一维直接递推即可. 时间复杂度: \(O(n \times 2^{2n})\)
我们注意到, 对于一个数\(n\), 其大于\(\sqrt{n}\)的质因数最多只有一个, 因此我们对小于\(500\)的质数进行分组, \(\le \sqrt{500}\)的分为一组, \(> \sqrt{500}\)的分为另一组, 则每个数至多只会包含一个第二组的质因数. 我们首先对第一组的素数按照前面的方法进行状压DP, 再考虑第二组.
我们对第二组中每个素数记录一个集合\(S\), 表示包含有这一个质因子的数的集合. 对于同一个\(S\)中的数, 要么两个人都不选, 要么只由一个人选. 因此对于一个集合, 我们用g[i = 0 / 1][j][k]来表示由\(i\)来选这个集合中的数, 且两个人所选小于等于\(\sqrt{n}\)的约数情况分别为\(j\), \(k\)的方案数. 开始时\(g[0 / 1][j][k] = f[j][k]\). 对于同一个集合中的一个元素\(a\), 我们有如下转移:
\]
当处理完一个集合中的数后, 我们更新\(f\)数组:
\]
其中\(f[j][k]\)表示更新前的\(f\)值. 将其减去的原因是\(g[0]\)和\(g[1]\)都计算了一次整个集合都不取的情况, 因此要减掉一次.
注意到有一些数不存在大于\(\sqrt{500}\)的因数, 我们把它们和小于等于\(\sqrt{500}\)的放在一起计算即可.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define min std::min
#define vector std::vector
const int N = 500;
int n, p;
int prm[N], isNotPrime[N + 1], cnt;
vector<int> bck[N];
inline void getPrime()
{
memset(isNotPrime, 0, sizeof(isNotPrime));
cnt = 0;
for(int i = 2; i <= 500; ++ i)
{
if(! isNotPrime[i]) prm[cnt ++] = i;
for(int j = 0; j < cnt && i * prm[j] <= 500; ++ j)
{
isNotPrime[i * prm[j]] = 1;
if(i % prm[j] == 0) break;
}
}
}
int main()
{
scanf("%d%d", &n, &p);
getPrime();
int bnd = 8;
int f[1 << bnd][1 << bnd]; memset(f, 0, sizeof(f)); f[0][0] = 1;
for(int i = 2; i <= min(n, 22); ++ i)
{
int stt = 0; for(int j = 0; j < bnd; ++ j) if(i % prm[j] == 0) stt |= 1 << j;
for(int j = (1 << bnd) - 1; ~ j; -- j) for(int k = (1 << bnd) - 1; ~ k; -- k)
f[j | stt][k] = (f[j | stt][k] + f[j][k]) % p, f[j][k | stt] = (f[j][k | stt] + f[j][k]) % p;
}
for(int i = 23; i <= n; ++ i)
{
int flg = 0;
for(int j = cnt - 1; j >= 8; -- j) if(i % prm[j] == 0)
{
flg = 1;
bck[j].push_back(i);
}
if(! flg)
{
int stt = 0; for(int j = 0; j < bnd; ++ j) if(i % prm[j] == 0) stt |= 1 << j;
for(int j = (1 << bnd) - 1; ~ j; -- j) for(int k = (1 << bnd) - 1; ~ k; -- k)
f[j | stt][k] = (f[j | stt][k] + f[j][k]) % p, f[j][k | stt] = (f[j][k | stt] + f[j][k]) % p;
}
}
int g[2][1 << bnd][1 << bnd];
for(int i = 8; i < cnt; ++ i) if(! bck[i].empty())
{
for(int j = 0; j < 2; ++ j) for(int k = 0; k < 1 << bnd; ++ k) for(int l = 0; l < 1 << bnd; ++ l) g[j][k][l] = f[k][l];
for(auto cur : bck[i])
{
int stt = 0; for(int j = 0; j < bnd; ++ j) if(cur % prm[j] == 0) stt |= 1 << j;
for(int j = (1 << bnd) - 1; ~ j; -- j) for(int k = (1 << bnd) - 1; ~ k; -- k)
g[0][j | stt][k] = (g[0][j | stt][k] + g[0][j][k]) % p, g[1][j][k | stt] = (g[1][j][k | stt] + g[1][j][k]) % p;
}
for(int j = 0; j < 1 << bnd; ++ j) for(int k = 0; k < 1 << bnd; ++ k) f[j][k] = ((g[0][j][k] + g[1][j][k]) % p - f[j][k] + p) % p;
}
int ans = 0;
for(int i = 0; i < 1 << bnd; ++ i) for(int j = 0; j < 1 << bnd; ++ j) if((i & j) == 0) ans = (ans + f[i][j]) % p;
printf("%d\n", ans);
}