【BZOJ4197】寿司晚宴

    这是一个DP题，然而人傻根本做不出来TAT

    考虑<=sqrt(n)的质数只有8个，那么>sqrt(n)的质数另外考虑，8个质数的集合用二进制表示。

    设f[i][j]为第一个人选的质数集合为i，第二个人选的质数集合为j时的方案数。g1[i][j]（g2[i][j]）分别表示第一个人（第二个人）选择当前考虑的寿司（可以不选）时的方案数。

    然后按照只含前8个质数，含第9个质数，含第10个质数等将这些数分类，然后开始DP。

    最后f[i][j]=g1[i][j]+g2[i][j]-f[i][j]，最后减去的f[i][j]是因为g1[i][j]和g2[i][j]都考虑了不选当前寿司的方案。

    膜Po姐...

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=510,k2=256,prime[8]={2,3,5,7,11,13,17,19},primes=8;
 
int f[k2][k2],g1[k2][k2],g2[k2][k2];
int n,p;
 
struct Info {int rest,state;}I[maxn];
bool cmp (const Info &a,const Info &b) {return a.rest<b.rest;}
 
int main()
{
    scanf("%d%d",&n,&p);
    for (int i=2;i<=n;i++)
    {
        int res=i;
        for (int j=0;j<primes;j++) if (res%prime[j]==0)
        {
            I[i].state|=(1<<j);
            while (res%prime[j]==0) res/=prime[j];
        }
        I[i].rest=res;
    }
    sort(I+2,I+n+1,cmp);
    f[0][0]=1;
    for (int l=2,r;l<=n;l++)
    {
        memcpy(g1,f,sizeof(f));
        memcpy(g2,f,sizeof(f));
        r=l;
        if (I[l].rest!=1) while (I[r+1].rest==I[l].rest) r++;
        for (int i=l;i<=r;i++)
            for (int a=255;a>=0;a--)
            for (int b=255;b>=0;b--)
            {
                if (!(I[i].state&b)) (g1[a|I[i].state][b]+=g1[a][b])%=p;
                if (!(I[i].state&a)) (g2[a][b|I[i].state]+=g2[a][b])%=p;
            }
        for (int a=255;a>=0;a--)
        for (int b=255;b>=0;b--)
            f[a][b]=((g1[a][b]+g2[a][b]-f[a][b])%p+p)%p;
        l=r;
    }
    int ans=0;
    for (int a=255;a>=0;a--)
    for (int b=255;b>=0;b--)
        (ans+=f[a][b])%=p;
    printf("%d\n",ans);
    return 0;
}