【bzoj4197】【NOI2015】寿司晚宴

题意

??有$n-1$个数从$【2，n】$，从中选出两个集合$S$和$U$（可以为$?$），要求对于$?x∈S，?y∈U$，都有$gcd（x，y）=1$，求方案总数（$n≤500$）

解法

状压$DP$：
??首先看到互质这一条件，可以想到利用质因子来判断
??很同意证明，对于一个数$x$，大于$\sqrt{x}$的质因子至多有一个。假设存在两个及两个以上大于$\sqrt{x}$的质因子：$p_1，p_2……p_n$，那么显然有$\prod_{i=1}^n p_i ＞x$，因此矛盾，得证
??那么我们可以将每个数分解质因数，单独记录那个大于$\sqrt{x}$的质因子，至于其他因子，我们可以用一个8位二进制数表示（因为满足$x≤\sqrt{500}≈22.3$的质数只有8个），所以就可以设立$DP$的状态：
??设$f_{i，j}$表示集合$S$的质因子包含情况为$i$，集合$U$的质因子包含情况为$j$的方案数，满足$i$&$j=0$，$g_{i，j，0/1}$表示集合$S$的质因子包含情况为$i$，集合$U$的质因子包含情况为$j$，并且那个大于$\sqrt{x}$的质因子在$S$/$U$之中的方案数
??$f_{i，j}=g_[i，j，0]+g_{i，j，1}-f_{i，j}$

复杂度

O（$2^8*2^8*n$）

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define Lint long long int
using namespace std;
const int MAXN=(1<<8)+100;
const int L=(1<<8)-1;
struct node
{int s,x;Lint pi;bool operator < (const node &a) const{return pi<a.pi;}
}t[MAXN*2];
Lint prime[8]={
   2,3,5,7,11,13,17,19};
Lint f[MAXN][MAXN],g[MAXN][MAXN][2];
Lint n,p,ans;
void init()
{for(int i=L;i>=0;i--)   for(int j=L;j>=0;j--)   g[i][j][0]=g[i][j][1]=f[i][j];
}
void write(int x)   { if( !x )   cout<<x; while( x )   cout<<(x&1),x/=2; }
int main()
{scanf("%lld%lld",&n,&p);Lint x;for(int i=2;i<=n;i++){x=(Lint)i,t[i].x=i;for(int j=0;j<=7 && prime[j]<=x;j++)if( !(x%prime[j]) ){t[i].s|=(1<<j);while( !(x%prime[j]) )   x/=prime[j];}if( x^1 )   t[i].pi=x;}sort( t+2,t+n+1 );f[0][0]=1;for(int i=2;i<=n;i++){if( t[i].pi!=t[i-1].pi || !t[i].pi )   init();for(int j=L;j>=0;j--)for(int k=L;k>=0;k--)if( !(j&k) ){if( !(t[i].s&k) )   g[t[i].s|j][k][0]=(g[t[i].s|j][k][0]+g[j][k][0])%p;if( !(t[i].s&j) )   g[j][t[i].s|k][1]=(g[j][t[i].s|k][1]+g[j][k][1])%p;}if( t[i].pi!=t[i+1].pi || !t[i].pi )for(int j=L;j>=0;j--)for(int k=L;k>=0;k--)if( !(j&k) )   f[j][k]=(g[j][k][0]+g[j][k][1]-f[j][k])%p;}for(int i=L;i>=0;i--)for(int j=L;j>=0;j--){if( i&j )   continue ;ans=(ans+f[i][j])%p;}printf("%lld\n",(ans+p)%p);return 0;
}