bzoj4197 [Noi2015]寿司晚宴—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4197

首先，两个人选的数都互质可以看作是一个人选了一个数，就相当于选了一个质因数集合，另一个人不能再选；

想把质因数状压起来，但是数量太多；

有个性质是一个数 x 最多有一个大于根号 x 的质因数，把那个拿出来单独考虑的话，剩下的质因数(小于根号500的)只有8个，可以状压；

于是先对2到 n 的每个数处理出单独的质因数和剩下的质因数状态，然后对单独质因数相同的几个数一起进行DP；

单独质因数相同，那么这几个数要么都被第一个人选，要么都被第二个人选，要么不被选；

所以用一个辅助数组 g 承接之前的 f 值，然后分成 g[0] 和 g[1] 分别表示第一个人选还是第二个人选，0和1之间不互相转移；

最后再把 f 赋回来，要注意这整个集合不被选的状态被算了两次，所以再减掉一个原来的值；

感觉自己好难想出来啊，尤其是那个辅助的 g 数组，但想好了却这么简洁。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=,mx=(<<);

int n,p,pri[]={,,,,,,,};

ll f[mx][mx],g[][mx][mx],ans;

struct N{int s,num;}a[maxn];

bool cmp(N x,N y){return x.num<y.num;}

void init()

{

    for(int i=;i<=n;i++)

    {

        int x=i;

        for(int j=;j<;j++)

        {

            if(x%pri[j])continue;

            a[i].s|=(<<j);

            while(x%pri[j]==)x/=pri[j];

        }

        a[i].num=x;

    }

}

int main()

{

    scanf("%lld%lld",&n,&p);

    init();

    sort(a+,a+n+,cmp);//a+2

    f[][]=;

    for(int i=;i<=n;i++)

    {

        if(i==||a[i].num!=a[i-].num||a[i].num==)//1表示没有大于根号n的质因子，所以每次重新DP

            memcpy(g[],f,sizeof f),memcpy(g[],f,sizeof f);

        for(int j=mx-;j>=;j--)

            for(int k=mx-;k>=;k--)//倒序

            {

                if(j&k)continue;

                if(!(a[i].s&k)) (g[][j|a[i].s][k]+=g[][j][k])%=p;

                if(!(a[i].s&j)) (g[][j][k|a[i].s]+=g[][j][k])%=p;

            }

        if(i==n||a[i].num!=a[i+].num||a[i].num==)

        {

            for(int j=mx-;j>=;j--)

                for(int k=mx-;k>=;k--)

//                    if(!(j&k)) (f[j][k]+=g[0][j][k]+g[1][j][k]-f[j][k])%=p;//已把之前f的值赋给g

                    if(!(j&k)) (f[j][k]=(g[][j][k]+g[][j][k]-f[j][k])%p+p)%p;//+p%p

        }

    }

    for(int j=mx-;j>=;j--)

        for(int k=mx-;k>=;k--)

            if(!(j&k)) (ans+=f[j][k])%=p;

    printf("%lld\n",ans);

    return ;

}

巴特西

bzoj4197 [Noi2015]寿司晚宴——状压DP

最新文章

热门文章