P2150 [NOI2015]寿司晚宴

题意：从$2-n$中选出两个集合，使得这两个集合的数两两互质（不包括集合内） 显然，选择一个数，相当于选择了ta的质因子 因此这两个集合的质因子是没有交集的 因为$n<=500$，小于√$500$的质因子只有8个 所以可以把状态压缩起来 ------------ 令$f[i][j]$表示第一个集合选择的质因子状态为$i$，第二个为$j$的方案数 DP前的初始化，先将$2-n$的每一个数分解质因子 用结构体记录下各自的状态和最后剩余的大因子 然后根据大因子从小到大排序，就把大因子相同的数放在了一起 确保了不会被两个集合同时选中 ------------ 在每一个大因子相同的范围内 将$f$数组复制到$a$和$b$中 $a$表示让第一个集合选择这个质因子，$b$同理 各自的转移方程为： $a[j|S][k]+=a[j][k](S\&k==0)$ $b[j][k|S]+=b[j][k](S\&j==0)$ 之后把$a$和$b$合并到$f$中 $f[j][k]=a[j][k]+b[j][k]-f[j][k]$ 注意要减去一个$f[j][k]$防止重复计算两个人都不选的情况 ------------ 那么最后答案就是把f数组统计总和就好了 **注意取模** ``` #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=505,M=260; int n,p; int prime[10]={0,2,3,5,7,11,13,17,19,23}; ll ans,f[M][M],a[M][M],b[M][M]; struct node { int val,num,S; inline void init() { int tmp=val; num=S=0; for (int i=1;i<=8;i++) { if (tmp%prime[i]) continue; S|=(1<<i-1); while (tmp%prime[i]==0) tmp/=prime[i]; } if (tmp!=1) num=tmp; } inline friend bool operator < (node a,node b) {return a.num<b.num;} }c[N]; int main() { scanf("%d%d",&n,&p); for (int i=1;i<n;i++) c[i].val=i+1,c[i].init(); sort(c+1,c+n); f[0][0]=1; for (int i=1;i<n;i++) { if (i==1||c[i].num>c[i-1].num||!c[i].num) { memcpy(a,f,sizeof(f)); memcpy(b,f,sizeof(f)); } for (int j=255;~j;j--) for (int k=255;~k;k--) { if (j&k) continue; if (!(c[i].S&j)) b[j][k|c[i].S]=(b[j][k|c[i].S]+b[j][k])%p; if (!(c[i].S&k)) a[j|c[i].S][k]=(a[j|c[i].S][k]+a[j][k])%p; } if (i==n-1||c[i].num<c[i+1].num||!c[i].num) { for (int j=0;j<256;j++) for (int k=0;k<256;k++) if (!(j&k)) f[j][k]=((a[j][k]+b[j][k])%p-f[j][k]+p)%p; } } for (int i=0;i<256;i++) for (int j=0;j<256;j++) if (!(i&j)) ans=(ans+f[i][j])%p; printf("%lld\n",ans); return 0; } ```