题目
题目链接：https://www.luogu.com.cn/problem/P2150
为了庆祝 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) 取模）。注意一个人可以不吃任何寿司。
(nleq 500,pleq 10^{10})。
思路
(500) 以内一共有 (95) 个质数，不好状压。
我们发现这其中每一个数超过 (lfloorsqrt{500}
floor=22) 的质因子只会有一个。我们设 (d_i) 为数字 (i) 超过 (22) 的质因子。然后把数字按照 (d_i) 排序。
显然这样对于每一段 (d_i) 相同的，这些数字只能由同一个人拿。
这样剩余的不超过 (22) 的质数就只有 (8) 个了。考虑状压。把每一段分别 dp。设 (f[0/1][i][j][k]) 表示选到第 (i) 个数，第一个人的质因子集合是 (j)，第二个人的质因子集合是 (k) 时，这一段由第一个人还是第二个人拿的方案数。转移就枚举上一次的状态。预处理出每一个数的不超过 (22) 的质因子集合。空间可以以把 (i) 这一维滚动
注意当处理完一段之后需要合并。设 (g[i][j]) 表示处理完一段后，第一个人质因子集合为 (i)，第二个人为 (j) 的方案数。然后与 (f) 合并就可以了。
时间复杂度 (O(2^{16}n))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int prm[8]={2,3,5,7,11,13,17,19};
const int N=510,M=(1<<8);
int n,a[N],s[N],d[N];
ll ans,MOD,f[2][2][M][M],g[M][M];
bool cmp(int x,int y)
{
return d[x]<d[y];
}
int main()
{
scanf("%d",&n);
scanf("%lld",&MOD);
for (int i=2;i<=n;i++)
{
int p=i;
for (int j=0;j<=7;j++)
if (!(p%prm[j]))
{
s[i]|=(1<<j);
while (!(p%prm[j])) p/=prm[j];
}
d[i]=p; a[i]=i;
}
sort(a+2,a+1+n,cmp);
g[0][0]=1;
for (int l=2;l<=n;l++)
{
int id=(l&1),i=a[l];
if (d[i]!=d[a[l-1]] || d[i]==1)
{
for (int j=0;j<M;j++)
for (int k=0;k<M;k++)
{
if (l!=2)
g[j][k]=(f[0][id^1][j][k]+f[1][id^1][j][k]-g[j][k])%MOD;
f[0][id^1][j][k]=f[1][id^1][j][k]=g[j][k];
}
}
for (int j=0;j<M;j++)
for (int k=0;k<M;k++)
{
f[0][id][j][k]=f[0][id^1][j][k];
f[1][id][j][k]=f[1][id^1][j][k];
}
for (int j=0;j<M;j++)
for (int k=0;k<M;k++)
{
if (!(k&s[i])) (f[0][id][j|s[i]][k]+=f[0][id^1][j][k])%=MOD;
if (!(j&s[i])) (f[1][id][j][k|s[i]]+=f[1][id^1][j][k])%=MOD;
}
}
int id=(n&1);
for (int i=0;i<M;i++)
for (int j=0;j<M;j++)
{
g[i][j]=(f[0][id][i][j]+f[1][id][i][j]-g[i][j])%MOD;
ans=(ans+g[i][j])%MOD;
}
printf("%lld",(ans%MOD+MOD)%MOD);
return 0;
}