题意
有序列 \(2,3,4\cdots n\)，对于序列中的每一个数，它可以被放入两个集合中的任意一个，或者不选。最后需要满足两个集合间的数两两互质（集合内部的数不需要满足互质），求方案数。
\(2 \leq n \leq 500\)。
思路
注意到 \(n\) 的范围很小，不难想到枚举质数出现状态的方式。可以预处理出每个数中质数出现的情况。
对于 \(n \leq 30\) 的部分，一共只有 \(10\) 个质数，那么设 \(f_{i,x,y}\) 为前 \(i\) 个数中，第一个集合的质数状态为 \(x\)，第二个集合的质数状态为 \(y\) 的方案数。转移只需要判断一下接下来的这个数是否能加入这两个集合中即可。时间复杂度为 \(O(n2^{10})\)
而对于 \(n \leq 500\) 的部分，直接枚举所有质数的时间复杂度显然不能接受。注意到 \(23 \times 23 >500\)，那么也就是每个数中至多含有一个大于 \(23\) 的质数，设这个质数为 \(p\)，那么对于所有含 \(p\) 的数构成的集合 \(S\)，\(S\) 至多只能选择一个数放在两个集合其中之一，再判断一下小于 \(23\) 的质数状态即可。
直接转移的空间复杂度比较大，可以用滚动数组优化一下。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=256;
int ans,f[N][N],f1[N][N],f2[N][N],n,p;
int prime[8]={2,3,5,7,11,13,17,19};
struct node{
int val,big,S;
void init(){
int tmp=val;big=-1;
for(int i=0;i<8;i++)
{
if(tmp%prime[i]) continue;S|=1<<i;
while(tmp%prime[i]==0) tmp/=prime[i];
}
if(tmp!=1) big=tmp;
}
}a[N];
bool cmp(node a,node b){return a.big<b.big;}
void Add(int &a,int b){a+=b;((a>=p)&&(a-=p));}
int main()
{
scanf("%d%d",&n,&p);for(int i=1;i<n;i++) a[i].val=i+1,a[i].init();sort(a+1,a+n,cmp);f[0][0]=1;
for(int i=1;i<n;i++)
{
if(i==1||a[i].big!=a[i-1].big||a[i].big==-1) memcpy(f1,f,sizeof(f1)),memcpy(f2,f,sizeof(f2));
for(int j=M-1;j>=0;j--) for(int k=M-1;k>=0;k--)
{
if(j&k) continue;
if(!(a[i].S&k)) Add(f1[j|a[i].S][k],f1[j][k]);
if(!(a[i].S&j)) Add(f2[j][k|a[i].S],f2[j][k]);
}
if(i==n-1||a[i].big!=a[i+1].big||a[i].big==-1)
{
for(int j=0;j<M;j++) for(int k=0;k<M;k++)
{
if(j&k) continue;
f[j][k]=(1ll*f1[j][k]+f2[j][k]-f[j][k]+p)%p;//注意都不选的情况被算了两次，要减去一次
}
}
}
for(int i=0;i<M;i++) for(int j=0;j<M;j++) if(!(i&j)) Add(ans,f[i][j]);printf("%d\n",ans);
return 0;
}