这题现场想的思路方向都是对的，但限于现场和实力因素没能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即可

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 8 using namespace std; 9 const int sp[8]={ 2,3,5,7,11,13,17,19};10 struct node{ int res,st;} a[510];11 12 int f[256][256],g[2][256][256];13 int ans,n,p;14 bool cmp(node a,node b)15 { 16 return a.res
            
             =0;u--)51 for (int v=255;v>=0;v--)52 if ((u&v)==0)53 {54 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;55 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; 56 } 57 i=j-1;58 }59 for (int u=0; u<256; u++)60 for (int v=0; v<256; v++)61 f[u][v]=((g[0][u][v]+g[1][u][v]-f[u][v])%p+p)%p;62 }63 for (int i=0; i<=255; i++)64 for (int j=0; j<=255; j++)65 if ((i&j)==0) ans=(ans+f[i][j])%p;66 printf("%d\n",ans);67 return 0;68 }