https://www.luogu.com.cn/problem/P2150
题解
前n个数（除去1）分到两组头，两组都要互质。
考虑30% 质数只有10个就可以状压f[i][j]表示第一组有状态为i的质数，第二组j有好多种方法。
显然f[i][j&s]+=f[i][j](!(i&s))
f[i&s][j]+=f[i][j](!(j&s))
f[0][0]=1;
考虑100%
发现500开跟22 22以内质数只有8个，而且超过22的质数不可能有两个出线在同一个数里。那我们记每个数的小质数状态s，大质数da。
吧所有大质数相同的排在一起，这样来保证这一个大质数只被同一个人选。
用三个数组转移
代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int n,mo,f1[N][N],f2[N][N],dp[N][N],zhi[10]={1,2,3,5,7,11,13,17,19};
struct pigu
{
int da,s;
}a[N];
inline int read()
{
char c=getchar();
int x=0,f=1;
while(!isdigit(c)) {if(c==‘-‘) f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<3)+(x<<1)+c-‘0‘;c=getchar();}
return x*f;
}
inline int add(int x,int y)
{
return x+y>mo?x+y-mo:x+y;
}
inline bool cmp(pigu x,pigu y)
{
return x.da<y.da;
}
signed main()
{
n=read();mo=read();
if(mo==1)
{
cout<<"0";
return 0;
}
for(int i=2;i<=n;i++)
{
int hu=i;
for(int j=1;j<=8;j++)
{
while(hu%zhi[j]==0)
{
hu/=zhi[j];
a[i].s|=(1<<j-1);
}
}
if(hu!=1) a[i].da=hu;
}
dp[0][0]=1;
sort(a+2,a+n+1,cmp);
for(int i=2;i<=n;i++)
{
if(a[i].da!=a[i-1].da||a[i].da==0)
{
for(int j=0;j<=255;j++)
for(int k=0;k<=255;k++)
f1[j][k]=f2[j][k]=dp[j][k];
}
for(int j=255;j>=0;j--)
for(int k=255;k>=0;k--)
if(!(j&k))
{
if(!(j&a[i].s)) f2[j][k|a[i].s]=add(f2[j][k|a[i].s],f2[j][k]);
if(!(k&a[i].s)) f1[j|a[i].s][k]=add(f1[j|a[i].s][k],f1[j][k]);
}
if(a[i].da!=a[i+1].da||a[i].da==0||i==n)
{
for(int j=0;j<=255;j++)
for(int k=0;k<=255;k++)
if(!(j&k))
{
dp[j][k]=add(mo-dp[j][k],add(f1[j][k],f2[j][k]));
}
}
}
int ans=0;
for(int i=0;i<=255;i++) for(int j=0;j<=255;j++) if(!(i&j))ans=add(ans,dp[i][j]);
cout<<ans;
}
原文：https://www.cnblogs.com/betablewaloot/p/12339756.html