点击这里查看原题
因为小于sqrt(500)的素数只有8个，而一个数大于sqrt(500)的素因子最多只有一个，因此可以将所有数分类，用一个二进制的8位数表示出现了哪些素因子，kind表示这个数的大于sqrt(500)的素因子，若不存在，则kind=1。将所有数按kind排序。 进行状压DP，f[i][j]表示1采用i方案，2采用j方案的方法数；p[i][j][k]表示该第i个人操作，1采用i方案，2采用j方案的方法书。每次如果取出的数的kind发生改变，则将f数组复制到p[1]和p[2]，最后用p数组更新f数组，f[j][k]=p[1][j][k]+p[2][j][k]-f[j][k]。 注意，任何取模操作和位运算都要小心，偷懒容易导致WA。
/* User:Small Language:C++ Problem No.:4197 */ #include<bits/stdc++.h> #define ll long long #define inf 999999999 using namespace std; int n,mod,prime[8]={2,3,5,7,11,13,17,19},f[256][256],p[3][256][256],ans; struct no{ int se,typ; }num[505]; bool cmp(no a,no b){ return a.typ==b.typ?a.se<b.se:a.typ<b.typ; } int main(){ freopen("data.in","r",stdin);// scanf("%d%d",&n,&mod); for(int i=1;i<=n;i++){ int tmp=i; for(int j=0;j<8;j++){ if(tmp%prime[j]==0){ num[i].se|=1<<j; while(tmp%prime[j]==0) tmp/=prime[j]; } } num[i].typ=tmp; } sort(num+2,num+n+1,cmp); f[0][0]=1; for(int i=2;i<=n;i++){ if(i==2||num[i].typ==1||num[i].typ!=num[i-1].typ){ memcpy(p[1],f,sizeof(p[1])); memcpy(p[2],f,sizeof(p[2])); } for(int j=255;j>=0;j--){ for(int k=255;k>=0;k--){ if((num[i].se&k)==0) p[1][j|num[i].se][k]=(p[1][j|num[i].se][k]+p[1][j][k])%mod; if((num[i].se&j)==0) p[2][j][k|num[i].se]=(p[2][j][k|num[i].se]+p[2][j][k])%mod; } } if(i==n||num[i].typ==1||num[i].typ!=num[i+1].typ){ for(int j=0;j<256;j++) for(int k=0;k<256;k++) f[j][k]=((p[1][j][k]+p[2][j][k]-f[j][k])%mod+mod)%mod; } } for(int i=0;i<256;i++) for(int j=0;j<256;j++) if((i&j)==0) ans=(ans+f[i][j])%mod; printf("%d\n",ans); return 0; }