LuoguP2150 [NOI2015]寿司晚宴

LuoguP2150 [NOI2015]寿司晚宴

题意：

链接

题解：

考虑暴力状压，发现显然过不了

然后套路根号分治

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    int f = 1,x = 0;
    char ch;
    do
    {
        ch = getchar();
        if(ch == '-') f = -1;
    }while(ch < '0'||ch > '9');
    do
    {
        x = (x<<3) +(x<<1) + ch - '0';
        ch = getchar();
    }while(ch >= '0'&&ch <= '9');
    return f*x;
}

const int MAXN = 500 + 2;

const int Prime[10] = {0,2,3,5,7,11,13,17,19};
int n,p;

struct node
{
    int sta;
    int P;
    friend bool operator < (node a1,node a2)
    {
        return a1.P < a2.P;
    }
}a[MAXN];

int dp[2][(1<<8) + 1][(1<<8) + 1];
int f[(1<<8) + 1][(1<<8) + 1];

int main()
{
    n = read(),p = read();
    for(int i=2;i<=n;i++)
    {
        int cur = i;
        for(int j=1;j<=8;j++) 
        {
            if(cur % Prime[j]) continue;
            while(cur % Prime[j] == 0) cur /= Prime[j];
            a[i-1].sta |= (1<<j-1);
        }
        a[i-1].P = cur == 1 ? -1 : cur;
    }
    sort(a+1,a+n);
    f[0][0] = 1;
    for(int i=1;i<n;i++)
    {
        if(a[i].P == -1 || a[i].P != a[i-1].P) 
        {
            memcpy(dp[0],f,sizeof(f));
            memcpy(dp[1],f,sizeof(f));
        }
        for(int sta1 = (1<<8)-1;sta1>=0;sta1--)
        {
            for(int sta2 = (1<<8)-1;sta2>=0;sta2--)
            {
                if(sta1 & sta2) continue;
                if((a[i].sta & sta2) == 0) dp[0][sta1|a[i].sta][sta2] = (dp[0][sta1|a[i].sta][sta2] + dp[0][sta1][sta2]) % p; 
                if((a[i].sta & sta1) == 0) dp[1][sta1][sta2|a[i].sta] = (dp[1][sta1][sta2|a[i].sta] + dp[1][sta1][sta2]) % p;            
            }
        }
        if(i == n - 1 || a[i].P != a[i+1].P || a[i].P == -1)
        {
            for(int sta1 = (1<<8)-1;sta1>=0;sta1--)
            {
                for(int sta2 = (1<<8)-1;sta2>=0;sta2--)
                {
                    if(sta1 & sta2) continue;
                    f[sta1][sta2] = ((dp[0][sta1][sta2] + dp[1][sta1][sta2] - f[sta1][sta2]) % p + p) % p;
                }
            }            
        }
    }
    long long ans = 0;
    for(int sta1 = (1<<8)-1;sta1>=0;sta1--)
    {
        for(int sta2 = (1<<8)-1;sta2>=0;sta2--)
        {
            if(sta1 & sta2) continue;
            ans += f[sta1][sta2]; 
            ans %= p;
        }
    }
    cout << ans << endl;
}