这题现场想的思路方向都是对的，但限于现场和实力因素没能A
很显然我们会想到质因数的选取
如果某个质数p被W选了，那G就不能选含有质因子p的数
因此我们不难想到状压质数的选取情况，令f[i][j]为w质数选取状态为i，g质数选取状态j的方案数
但是500以内质数太多了怎么办？我们考虑大质数能不能分开考虑
考虑到sqrt(500)以外的质数，他们在每个数中最多出现一次，因此我们只要按这些质数分类做dp即可
这样需要状压的质数只有2，3，5，7，11，13，17，23这8个了，这样就可以解决了
具体的，我用state表示每个数前8个质数的含有情况，res表示除去前8个质数剩下的数
然后按照res排序做dp即可
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm> using namespace std;
const int sp[]={2,3,5,7,11,13,17,19};
struct node{int res,st;} a[]; int f[][],g[][][];
int ans,n,p;
bool cmp(node a,node b)
{
return a.res<b.res;
}
int main()
{
scanf("%d%d",&n,&p);
for (int i=2; i<=n; i++)
{
int x=i;
for (int j=0; j<8; j++)
if (x%sp[j]==0)
{
a[i].st+=1<<j;
while (x%sp[j]==0) x/=sp[j];
}
a[i].res=x;
}
sort(a+,a++n,cmp);
f[][]=g[][][]=g[][][]=;
for (int i=; i<=n; i++)
{
memcpy(g[0],f,sizeof(f));
memcpy(g[1],f,sizeof(f));
for (int u=0; u<256; u++)
for (int v=0; v<256; v++)
if ((u&v)==0)
{
if ((a[i].st&v)==0) g[0][u|a[i].st][v]=(g[0][u|a[i].st][v]+f[u][v])%p;
if ((a[i].st&u)==0) g[1][u][v|a[i].st]=(g[1][u][v|a[i].st]+f[u][v])%p;
} if (a[i].res!=)
{
int j;
for (j=i+1; j<=n&&a[j].res==a[i].res; j++)
for (int u=255;u>=0;u--)
for (int v=255;v>=0;v--)
if ((u&v)==0)
{
if ((a[j].st&v)==0) g[0][u|a[j].st][v]=(g[0][u|a[j].st][v]+g[0][u][v])%p;
if ((a[j].st&u)==0) g[1][u][v|a[j].st]=(g[1][u][v|a[j].st]+g[1][u][v])%p;
}
i=j-;
}
for (int u=; u<; u++)
for (int v=; v<; v++)
f[u][v]=((g[][u][v]+g[][u][v]-f[u][v])%p+p)%p;
}
for (int i=; i<=; i++)
for (int j=; j<=; j++)
if ((i&j)==) ans=(ans+f[i][j])%p;
printf("%d\n",ans);
return ;
}