P2150 [NOI2015] 寿司晚宴
思路：
注意到对于每个数，其 \(>19\) 的质因数最多只有 \(1\) 个，称为大质数；对于 \(\le 19\) 的质因数有 \(8\) 个，称为小质数。
设第 \(i\) 个数的小质数集合为 \(h_i\)。
那么考虑对于所有数按照大质数从小到大排序，那么对于大质数相同的一段，只能放在两个集合中的一个。
考虑状态压缩 \(dp\)，定义 \(dp_{S_1,S_2}\) 表示对于取完 \(i\)（可以滚动数组） 个数后第一/二个集合的小质数集合，\(f1_{S_1,S_2}\) 表示这一段的数都放在第一个集合的方案数，\(f2_{S_1,S_2}\) 表示这一段的数都放在第二个集合的方案数。
则状态转移方程为（首先要满足 \(S_1\) 与 \(S_2\) 没有交集，即 \(S_1 \operatorname{and} S_2 = 0\)）：
\[f1_{S_1 \operatorname{or} data_i,S_2} += f1_{S_1,S_2} [S_2 \operatorname{and} h_i = 0]
\]
\[f2_{S_1,S_2 \operatorname{or} data_i} += f1_{S_1,S_2} [S_1 \operatorname{and} h_i = 0]
\]
\[dp_{S_1,S_2} = f1_{S_1,S_2} + f2_{S_1,S_2} - dp_{S_1,S_2}
\]
因为 \(f1\) 和 \(f2\) 都可以不取这一段的数，那么 \(dp_{S_1,S_2}\) 就被算了两次，减掉即可。
时间复杂度为 \(O(n2^{16})\)。
完整代码：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=505,M=8,S=(1ll<<M);
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
struct Node{
ll x;
ll data;
bool operator<(const Node&rhs)const{
return x<rhs.x;
}
}a[N];
ll n,x,ans,mod;
ll dp[S][S],f1[S][S],f2[S][S];
ll P[]={2,3,5,7,11,13,17,19};
bool End;
int main(){
n=read(),mod=read();
for(int i=2;i<=n;i++){
x=i;
for(int j=0;j<8;j++){
if(x%P[j]==0){
a[i].data|=(1ll<<j);
while(x%P[j]==0)
x/=P[j];
}
}
if(x!=1)
a[i].x=x;
}
dp[0][0]=1;
sort(a+2,a+n+1);
for(int i=2;i<=n;i++){
if(!a[i].x||a[i].x!=a[i-1].x){
for(int X=0;X<S;X++)
for(int Y=0;Y<S;Y++)
f1[X][Y]=f2[X][Y]=dp[X][Y];
}
for(int X=S-1;X>=0;X--){
for(int Y=S-1;Y>=0;Y--){
if(X&Y)
continue;
if((a[i].data&Y)==0)
f1[X|a[i].data][Y]=Add(f1[X|a[i].data][Y],f1[X][Y]);
if((a[i].data&X)==0)
f2[X][Y|a[i].data]=Add(f2[X][Y|a[i].data],f2[X][Y]);
}
}
if(i==n||a[i].x!=a[i+1].x||!a[i].x){
for(int X=0;X<S;X++)
for(int Y=0;Y<S;Y++)
dp[X][Y]=(f1[X][Y]+f2[X][Y]-dp[X][Y]+mod)%mod;
}
}
for(int X=0;X<S;X++)
for(int Y=0;Y<S;Y++)
ans=Add(ans,dp[X][Y]);
write(ans);
cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
return 0;
}