P2150 [NOI2015] 寿司晚宴
翻译一下，题目其实就是给你\(2-n\)这些数，从其中选出两个集合（可以为空），求使两个集合中的数两两互质的方案数。
那么就相当于说两个集合中的数的质因数的集合不能有重合。
先看前\(\%30\)的数据，\(n<=30\)，里面的质因数不多，考虑状压\(DP\)。
我们不妨设\(DP[i][S_1][S_2]\)表示在前\(i\)个数中，第一个集合的质因数集合为\(S_1\)，第二个为\(S_2\)的情况下的方案数。
状态转移：（\(k\)表示第\(i\)个数的质因子集合）
\(DP[~i~][~S_1|k~][~S_2~]~=~DP[~i-1~][~S_1~][~S_2~]+DP[~i~][~S_1|k~][~S_2~]~(S_2\&k=0)\)
\(DP[~i~][~S_1~][~S_2|k~]=DP[~i-1~][~S_1~][~S_2~]+DP[~i~][~S_1~][~S2|k~]~(S_1\&k=0)\)
由于每一个\(DP[i]\)之和\(DP[i-1]\)有关，且\(DP[i][S_1][S_2]\)只会从\(DP[i-1][S_1'][S_2']（S_1>=S_1'~;~S_2>=S_2'）\)转移，所以可以降维优化，将\(S_1,S_2\)倒着枚举即可。
接着我们考虑全部的数据范围。
可是，小于\(500\)的质因子太多了，状压绝对会超空间。
但是我们发现，\(500\)以内的数最多有一个质因子\(>22\)（我们称其大因子）（因为一个数\(x\)最多只有一个质因子\(>\sqrt{x}\)，而\(\sqrt{500}=22\)），而小于\(22\)的质因子只有\(8\)个，满足状压。
我们先预处理，把大因子相同的放在一起，由于相同大因子的数不能放在一起，那么设置\(F_1[S_1][S_2],F_2[S_1][S_2]\)，分别表示只把相同大因子放第一个集合或第二个集合的情况，状态转移方程同上。
而当相同大因子的数处理完后，要把他们合并到\(DP\)数组里，公式为：\(DP[S_1][S_2]=F_1[S_1][S_2]+F_2[S_1][S_2]-DP[S_1][S_2]\)。
之所以要减去一个\(DP[S_1][S_2]\)，是因为\(F_1\)和\(F_2\)中都计算了一次相同大因子的数一个都不选的情况，需要减去一个（由于采取了降维优化，这里的\(DP[S_1][S_2]\)记录的是未考虑大因子为当前大因子的数的情况）。
需要注意的是，若考虑完了一个大因子的所有数后开始考虑下一个，或者当前数没有大因子时，需要把\(F_1,F_2\)赋值为\(DP\)。（相当于开始了新的一轮\(DP\)，之前的\(F_1,F_2\)应该更新掉）。
最后把每种合法状态的和做一个和即可。
#include<bits/stdc++.h>
#define m_p make_pair
#define ll long long
using namespace std;
const int N=501,MAXN=260;
ll p;
int n;
int prime[8]={2,3,5,7,11,13,17,19};
struct node{
int val,cnt,two;
}a[N];
ll dp[MAXN][MAXN],f1[MAXN][MAXN],f2[MAXN][MAXN];
bool cmp(node x,node y){
return x.cnt>y.cnt;
}
void ask(int i){
int tmp=a[i].val;
for(int j=0;j<8;j++){
if(tmp%prime[j]==0){
while(!(tmp%prime[j])) tmp/=prime[j];
a[i].two|=(1<<j);
}
}
a[i].cnt=tmp;
}
int main(){
scanf("%d%lld",&n,&p);
for(int i=2;i<=n;i++){
a[i-1].val=i;
ask(i-1);
}
sort(a+1,a+n,cmp);
dp[0][0]=1;
for(int i=1;i<n;i++){
if(i==1||a[i].cnt==1||a[i].cnt!=a[i-1].cnt){//更新
memcpy(f1,dp,sizeof(dp));
memcpy(f2,dp,sizeof(dp));
}
for(int j=255;j>=0;j--){//注意，需要逆推
for(int k=255;k>=0;k--){
if(j&k) continue;
if(!(j&a[i].two))f1[j][k|a[i].two]=(f1[j][k|a[i].two]+f1[j][k])%p;
if(!(k&a[i].two))f2[j|a[i].two][k]=(f2[j|a[i].two][k]+f2[j][k])%p;
}
}
if(a[i].cnt==1||i==n-1||a[i].cnt!=a[i+1].cnt){//合并
for(int j=0;j<=255;j++){
for(int k=0;k<=255;k++){
if(j&k) continue;
dp[j][k]=((f1[j][k]+f2[j][k])%p-dp[j][k]+p)%p;
}
}
}
}
//统计答案：
ll ans=0;
for(int j=0;j<=255;j++){
for(int k=0;k<=255;k++){
if(j&k) continue;
ans=(ans+dp[j][k])%p;
}
}
cout<<ans;
return 0;
}