[NOI2015] 寿司晚宴

Description

给定 $n-1$ 种物品，重要度分别为 $[2,n]$ 。甲乙两者来拿若干件（可以为 $0$）物品。若甲拿的物品的重要度集合为 $S_1$ ，乙拿的物品的重要度集合为$S_2$ ，则一种合法的方案定义为 $\forall x\in S_1,\forall y\in S_2,\gcd(x,y)=1$ 。求拿物品的方案总数对 $p$ 取模的值。
$n\leq 500$

Solution

既然两个集合的唯一限制是质因子无交集，那么不难往状压DP方面去思考。压 $500$ 以内的全部质数？不是很可做的亚子，我们必须思考如何压缩状态。

状压DP非常重要的一点就是把本来看上去不可以压的东西通过一些小 trick 使得一些东西可以单独拿出来。比如在这个题目中，一个数不可能同时有两个大于 $19$ 的质因数！

也就是说，当我们考虑某个质数 $p(p>19)$ 时，我们只需注意所有小于等于 $19$ 的质数及该质数满足条件，其他的质数可以暂时不作考虑。故我们只需要压 $19$ 以内的质数——很幸运，只有 $8$ 个。具体处理的时候，我们先将所有数按照最大的质数排序，大质数相同的一起处理。设两个数组 f1[][] 和 f2[][] ，分别表示当前质数只放在甲手里/只放在乙手里。于是就可以实现DP啦。

Code

for(int i=2;i<=n;++i){
	if(!a[i].BIG||i==2||a[i].BIG!=a[i-1].BIG)
		memcpy(f1,dp,sizeof dp),memcpy(f2,dp,sizeof dp);
	for(int j=d;j>=0;--j)
	for(int k=d;k>=0;--k){
		if(j&k) continue;
		if(!(a[i].s&k)) f1[j|a[i].s][k]=A(f1[j|a[i].s][k],f1[j][k]);
		if(!(a[i].s&j)) f2[j][k|a[i].s]=A(f2[j][k|a[i].s],f2[j][k]);
	}
	if(!a[i].BIG||i==n||a[i].BIG!=a[i+1].BIG){
		for(int j=d;j>=0;--j)
		for(int k=d;k>=0;--k)
			if(!(j&k))
				dp[j][k]=A(f1[j][k],A(f2[j][k],p-dp[j][k]));
	}
}