P2150 [NOI2015]寿司晚宴

2018-09-03 18:50:56


题意:从 $2-n$ 中选出两个集合,使得这两个集合的数两两互质(不包括集合内)

显然,选择一个数,相当于选择了ta的质因子

因此这两个集合的质因子是没有交集的

因为 $n<=500$ ,小于√ $500$ 的质因子只有8个

所以可以把状态压缩起来


令 $f[i][j]$ 表示第一个集合选择的质因子状态为 $i$ ,第二个为 $j$ 的方案数

DP前的初始化,先将 $2-n$ 的每一个数分解质因子

用结构体记录下各自的状态和最后剩余的大因子

然后根据大因子从小到大排序,就把大因子相同的数放在了一起

确保了不会被两个集合同时选中


在每一个大因子相同的范围内

将 $f$ 数组复制到 $a$ 和 $b$ 中

$a$ 表示让第一个集合选择这个质因子, $b$ 同理

各自的转移方程为:

$a[j|S][k]+=a[j][k](S\&k==0)$

$b[j][k|S]+=b[j][k](S\&j==0)$

之后把 $a$ 和 $b$ 合并到 $f$ 中

$f[j][k]=a[j][k]+b[j][k]-f[j][k]$

注意要减去一个 $f[j][k]$ 防止重复计算两个人都不选的情况


那么最后答案就是把f数组统计总和就好了

注意取模

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=505,M=260;
int n,p;
int prime[10]={0,2,3,5,7,11,13,17,19,23};
ll ans,f[M][M],a[M][M],b[M][M];
struct node
{
    int val,num,S;
    inline void init()
    {
        int tmp=val; num=S=0;
        for (int i=1;i<=8;i++)
        {
            if (tmp%prime[i]) continue;
            S|=(1<<i-1);
            while (tmp%prime[i]==0) tmp/=prime[i];
        }
        if (tmp!=1) num=tmp;
    }
    inline friend bool operator < (node a,node b) {return a.num<b.num;}
}c[N];
int main()
{
    scanf("%d%d",&n,&p);
    for (int i=1;i<n;i++) c[i].val=i+1,c[i].init();
    sort(c+1,c+n); f[0][0]=1;
    for (int i=1;i<n;i++)
    {
        if (i==1||c[i].num>c[i-1].num||!c[i].num)
        {
            memcpy(a,f,sizeof(f)); 
            memcpy(b,f,sizeof(f));
        }
        for (int j=255;~j;j--)
          for (int k=255;~k;k--)
          {
              if (j&k) continue;
              if (!(c[i].S&j)) b[j][k|c[i].S]=(b[j][k|c[i].S]+b[j][k])%p;
              if (!(c[i].S&k)) a[j|c[i].S][k]=(a[j|c[i].S][k]+a[j][k])%p;
          }
        if (i==n-1||c[i].num<c[i+1].num||!c[i].num)
        {
            for (int j=0;j<256;j++)
              for (int k=0;k<256;k++)
                if (!(j&k)) f[j][k]=((a[j][k]+b[j][k])%p-f[j][k]+p)%p;
        }
    }
    for (int i=0;i<256;i++)
      for (int j=0;j<256;j++) 
        if (!(i&j)) ans=(ans+f[i][j])%p;
    printf("%lld\n",ans);
    return 0;
}