寿司晚宴题解
先理解一下题目吧:
两人所选数的质因数集合不能有交集,
<=30的质数只有10个,所以可以直接状压,
\(dp[i][j]\)代表第一个人选的状态为i,第二个人的状态为j的方案数,
100%:n由30拓展到了500,怎么办?
考虑到<=500的数最多只有1个大于\(sqrt(500)>22\)的大质因子,
我们可以按大质因子排序,想同的大质因子里用,用dp表示选了它的情况,用dp2表示没选的情况,然后转移,
不同的时候就继承之前的值.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=506,N=266;
int n,m,tot=0,book[M],prime[M];
ll ans=0,p,f[N][N],dp[N][N],dp2[N][N];
struct xd{int a,b;}q[M];
void init(){
for(int i=2;i<=500;++i){
if(!book[i]) prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=500;++j){
book[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
bool cmp(xd u,xd v){return u.b<v.b;}
int main(){
scanf("%d%lld",&n,&p),m=255,init();
for(int i=2;i<=n;++i){
for(int j=9;j<=tot;++j) if(i%prime[j]==0) q[i-1].b=prime[j];
for(int j=0;j<=7;++j) if(i%prime[j+1]==0) q[i-1].a+=(1<<j);
}
sort(q+1,q+n,cmp),f[0][0]=1,q[0].b=q[n].b=-1;
for(int i=1;i<n;++i){
if(q[i].b!=q[i-1].b||!q[i].b) memcpy(dp,f,sizeof(dp)),memcpy(dp2,f,sizeof(dp2));
for(int j=m;j>=0;--j)
for(int k=m;k>=0;--k){
if(j&k) continue;
if(!(q[i].a&k)) dp[j|q[i].a][k]=(dp[j|q[i].a][k]+dp[j][k])%p;
if(!(q[i].a&j)) dp2[j][k|q[i].a]=(dp2[j][k|q[i].a]+dp2[j][k])%p;
}
if(q[i].b!=q[i+1].b||!q[i].b) for(int j=m;j>=0;--j) for(int k=m;k>=0;--k) f[j][k]=(dp[j][k]+dp2[j][k]-f[j][k]+p)%p;
}
for(int i=m;i>=0;--i) for(int j=m;j>=0;--j) ans=(ans+f[i][j])%p;
printf("%lld\n",ans);
return 0;
}