讲解 P2150 [NOI2015] 寿司晚宴。

使用状态压缩动态规划，抓住特殊性质进行 dp。

思路：

注意到对于每个数，其 \(>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})\)。

完整代码：

<code>#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;

}