NOI 2015 寿司晚宴 (状压DP+分组背包)

题目大意：两个人从2~n中随意取几个数(不取也算作一种方案)，被一个人取过的数不能被另一个人再取。两个人合法的取法是，其中一个人取的任何数必须与另一个人取的每一个数都互质，求所有合法的方案数

(数据范围毕竟很小，乍一看也不是啥打表找规律的题)

和我之前做过的一道题很类似hdu 6125，但这道题由于题面看起来很玄学，所以正解更难想

但还是状压DP+分组背包的套路

因为500以内的任何一个数，只会有一个大于19的质因子，所以对2 3 5 7 11 13 17 19这8个质数进行状压，然后每个数都质因数分解，把小于等于19的质因子存入状态，剩下的因子分组背包搞搞就行了，注意如果剩下的因子是1要单独算一组，否则会出大事情，比如2和3并不是同一组的，如果再来一个4，和2是同一组的，转移就会出错

具体DP的实现呢，定义 $dp[s1][s2]$ 是第一个人取了状态为s1的数，第二个人取了状态为s2的数

分组背包要把同一组的东西放到连续的一段序列上

对于这道题而言，如果某个人取了某一组的任何一个，那么这一组的其它物品也只能被这个人取/不取

所以额外定义两个状态f1,f2，含义和dp的意义是一样的，只不过在同一组内是f1和f2这两个状态自己和自己转移，然后把答案贡献给dp，即这一组对整体的贡献，然后把dp重新赋给f1,f2，再进行下一组背包

方程 $f1[s1|K][s2]+=f1[s1][s2]$ $f2[s1][s2|K]+=f2[s1][s2]$

由于f1,f2为了下一层转移，都被加了一次dp值，所以最后要减掉一个dp

即 $dp[s1][s2]=f1[s1][s2]+f2[s1][s2]-dp[s1][s2]$

而f1,f2转移也有技巧，常规的自己和自己转移为了避免传递性，要另外开一个数组进行转移。但因为这道题的转移方程都是位与|操作，具有递增性，所以倒序枚举就可以减少一些常数

 1 #include <queue>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define ui unsigned int
 6 #define ll long long 
 7 #define il inline
 8 #define N (1<<8)+3
 9 #define inf 0x3f3f3f3f
10 using namespace std;
11 
12 int n;
13 ll p;
14 ll f1[N][N],f2[N][N],dp[N][N];
15 int pr[]={2,3,5,7,11,13,17,19};
16 struct node{
17     int w,f;
18     friend bool operator < (const node &a,const node &b){
19         if(a.w!=b.w) return a.w<b.w;
20         else return a.f<b.f;
21     }
22 }s[N];
23 void get_son()
24 {
25     for(int i=2;i<=n;i++)
26     {
27         int x=i;
28         for(int j=0;j<8;j++)
29         {
30             if(x%pr[j]==0) x/=pr[j],s[i].f|=(1<<j);
31             while(x%pr[j]==0) x/=pr[j];
32         }s[i].w=x;
33     }
34 }
35 
36 int main()
37 {
38     scanf("%d%lld",&n,&p);
39     get_son();
40     sort(s+2,s+n+1);
41     f1[0][0]=f2[0][0]=dp[0][0]=1;
42     int m=(1<<8)-1;
43     for(int i=2;i<=n;i++)
44     {
45         for(int s1=m;s1>=0;s1--)
46             for(int s2=m;s2>=0;s2--){
47                 if(!((s1|s[i].f)&s2)) f1[s1|s[i].f][s2]=(f1[s1|s[i].f][s2]+f1[s1][s2])%p;
48                 if(!(s1&(s2|s[i].f))) f2[s1][s2|s[i].f]=(f2[s1][s2|s[i].f]+f2[s1][s2])%p;}
49         if(s[i].w==1||s[i+1].w!=s[i].w)
50             for(int s1=m;s1>=0;s1--)
51                 for(int s2=m;s2>=0;s2--)
52                     f1[s1][s2]=f2[s1][s2]=dp[s1][s2]=(f1[s1][s2]+f2[s1][s2]-dp[s1][s2]+p)%p;
53     }
54     ll ans=0;
55     for(int s1=m;s1>=0;s1--)
56         for(int s2=m;s2>=0;s2--)
57             ans+=dp[s1][s2],ans%=p;
58     printf("%lld
",ans);
59     return 0;
60 }