题目链接
反正……我是没什么想法了，全程看题解
（或者说自己想了半天错解）
因为大于根n的质数最多只会在一个数里出现一种，所以可以把数拆成两部分：小数的二进制集合和大数。
然后把大数一样的放到一起DP，设s[i][j]表示第一个集合为i第二个为j的方案数，f[i][j][k]是第一个集合为i第二个集合为j，当前数放进第k个集合里……
转移当然比我那个sb的二维状态好转移啦
#include<cstdio> #include<cctype> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define maxs 11 #define maxn 600 using namespace std;inline long long read(){long long num=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){num=num*10+ch-'0';ch=getchar();}return num*f; }int prime[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; int s[maxn][maxn],f[maxn][maxn][2];struct Number{int state,p;bool operator <(const Number a)const{return p<a.p;} }q[maxn];int main(){int n=read(),mod=read();for(int i=2;i<=n;++i){int ret=i;q[i-1].state=0;for(int j=1;j<9;++j){int now=prime[j];if(ret%now) continue;q[i-1].state|=(1<<(j-1));while(ret%now==0) ret/=now;}q[i-1].p=ret;}sort(q+1,q+n);s[0][0]=1;for(int i=1;i<n;++i){Number now=q[i];if(now.p==1||now.p!=q[i-1].p)for(int S1=0;S1<=256;++S1)for(int S2=0;S2<=256;++S2) f[S1][S2][0]=f[S1][S2][1]=s[S1][S2];for(int S1=256;S1>=0;--S1)for(int S2=256;S2>=0;--S2){if((now.state&S2)==0) f[now.state|S1][S2][0]=(1LL*f[now.state|S1][S2][0]+f[S1][S2][0])%mod;if((now.state&S1)==0) f[S1][now.state|S2][1]=(1LL*f[S1][now.state|S2][1]+f[S1][S2][1])%mod;}if(now.p==1||now.p!=q[i+1].p)for(int S1=0;S1<=256;++S1)for(int S2=0;S2<=256;++S2) s[S1][S2]=((1LL*f[S1][S2][0]+f[S1][S2][1])%mod-s[S1][S2]+mod)%mod;}int ans=0;for(int i=0;i<=256;++i)for(int j=0;j<=256;++j)if((i&j)==0) ans=(ans+s[i][j])%mod;printf("%d\n",ans);return 0; }
