【BZOJ4197】寿司晚宴（NOI2015）-状压DP+数论

测试地址：寿司晚宴
做法：本题需要用到状压DP+数论。
考虑 $n$ 小一点的情况，我们发现题目条件等价于两个人所选的数的质因子集合不相交，那么我们令 $f (i, j, k)$ 为考虑了前 $i$ 个数，其中第一个人取的数的质因子集合为 $j$ ，第二个人取的数的质因子集合为 $k$ 的方案数，状态转移方程应该很好写了，详见代码，用枚举子集的技巧就可以做到 $O (n 3^{p (n)})$ ，其中 $p (n)$ 为 $n$ 以内的质数个数。答案就是 $\sum_{j \cap k = \emptyset} f (n, j, k)$ 。
可是当 $n$ 更大的时候，显然上面的方法就会超时了，怎么办呢？我们发现每个数最多含有一个 $> \sqrt{n}$ 的质因子，这个性质非常好，我们可以分开考虑这个质因子为某个数 $x$ 时对答案的贡献。所以我们把 $\leq \sqrt{n}$ 的质因子状态压缩，接着先把不含有 $> \sqrt{n}$ 质因子的数拿出来按照上面的方法DP一遍，然后枚举大于 $\sqrt{n}$ 的质因子 $x$ ，令 $g (i, j, k)$ 为考虑了前 $i$ 个数，其中第一个人取的数的质因子集合为 $j$ （这里考虑的质因子集合包括当前枚举的 $x$ ），第二个人取的数的质因子集合为 $k$ 的方案数，那么首先：
$g (0, j, k) = f (p a s t, j, k)$
其中 $p a s t$ 为之前做完DP的部分。然后我们对包含质因子 $x$ 的数进行一遍和上面类似的DP，最后用新的部分更新已DP部分：
$f (n o w, j, k) = g (P a s t, j, k) + g (P a s t, j \cup {x}, k) + g (P a s t, j, k \cup {x})$
最后 $\sum_{j \cap k = \emptyset} f (p a s t, j, k)$ 就是答案。那么算法的总时间复杂度为 $O (n 3^{p (\sqrt{n})})$ ，可以通过此题。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,prime[510],limit,a[510]={0},num[510];
ll f[2][310][310]={0},g[2][550][550],mod;
bool vis[510]={0};

void calc_prime()
{
    prime[0]=0;
    for(int i=2;i<=n;i++)
    {
        if (!vis[i])
        {
            prime[++prime[0]]=i;
            if (i<=sqrt(n)) limit=prime[0];
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}

int main()
{
    scanf("%d%lld",&n,&mod);

    calc_prime();
    for(int i=2;i<=n;i++)
    {
        int x=i;
        for(int j=1;j<=limit;j++)
            if (i%prime[j]==0)
            {
                a[i]+=(1<<(j-1));
                while(x%prime[j]==0) x/=prime[j];
            }
        num[i]=x;
    }

    int now=1,past=0;
    f[past][0][0]=1;
    for(int i=2;i<=n;i++)
        if (num[i]==1)
        {
            memset(f[now],0,sizeof(f[now]));
            for(int j=0;j<(1<<limit);j++)
            {
                int anti=(1<<limit)-j-1;
                for(int k=anti;;k=(k-1)&anti)
                {
                    f[now][j][k]=(f[now][j][k]+f[past][j][k])%mod;
                    f[now][j|a[i]][k]=(f[now][j|a[i]][k]+f[past][j][k])%mod;
                    f[now][j][k|a[i]]=(f[now][j][k|a[i]]+f[past][j][k])%mod;
                    if (!k) break;
                }
            }
            swap(now,past);
        }

    for(int i=limit+1;i<=prime[0];i++)
    {
        int x=prime[i];
        int Now=1,Past=0;
        memset(g[Past],0,sizeof(g[Past]));
        for(int j=0;j<(1<<limit);j++)
        {
            int anti=(1<<limit)-j-1;
            for(int k=anti;;k=(k-1)&anti)
            {
                g[Past][j][k]=f[past][j][k];
                if (!k) break;
            }
        }
        for(int j=2;j<=n;j++)
            if (num[j]==x)
            {
                memset(g[Now],0,sizeof(g[Now]));
                for(int k=0;k<(1<<(limit+1));k++)
                {
                    int anti=(1<<(limit+1))-k-1;
                    for(int l=anti;;l=(l-1)&anti)
                    {
                        g[Now][k][l]=(g[Now][k][l]+g[Past][k][l])%mod;
                        g[Now][k|a[j]|(1<<limit)][l]=(g[Now][k|a[j]|(1<<limit)][l]+g[Past][k][l])%mod;
                        g[Now][k][l|a[j]|(1<<limit)]=(g[Now][k][l|a[j]|(1<<limit)]+g[Past][k][l])%mod;
                        if (!l) break;
                    }
                }
                swap(Past,Now);
            }
        for(int j=0;j<(1<<limit);j++)
        {
            int anti=(1<<limit)-j-1;
            for(int k=anti;;k=(k-1)&anti)
            {
                f[now][j][k]=(g[Past][j][k]+g[Past][j|(1<<limit)][k]+g[Past][j][k|(1<<limit)])%mod;
                if (!k) break;
            }
        }
        swap(now,past);
    }

    ll ans=0;
    for(int i=0;i<(1<<limit);i++)
    {
        int anti=(1<<limit)-i-1;
        for(int j=anti;;j=(j-1)&anti)
        {
            ans=(ans+f[past][i][j])%mod;
            if (!j) break;
        }
    }
    printf("%lld",ans);

    return 0;
}