LibreOJ 2131 「NOI2015」寿司晚宴

神题神题，今天来玩几道状压题。

首先考虑若 n≤20 怎么做：
显然记录一下质因子集合即可。

然而 n≤500，但是根据一些基本的数论知识，每个数最多只有一个超过 19 的质因子（下称大质因子）。
于是可以考虑每个数的大质因子预处理出来，然后把大质因子相同的放在一起处理。

具体地说，就是对于每个连续段，考虑把这个大质因子给小 G 或小 W，然后合并答案（注意不选大质因子的会被算两次，容斥掉）。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500;
const int P = 8;
const int prime[] = {0,2,3,5,7,11,13,17,19};
const int full = (1 << P) - 1;
int n;
long long mod,f[(1 << P) + 5][(1 << P) + 5],g[2][(1 << P) + 5][(1 << P) + 5],ans;
struct note
{
    int s,w;
    inline bool operator<(const note &o) const
    {
        return w < o.w;
    }
} a[N + 5];
int main()
{
    scanf("%d%lld",&n,&mod),f[0][0] = 1;
    for(register int i = 2,v;i <= n;++i)
    {
        v = i;
        for(register int j = 1;j <= P && v > 1;++j)
        {
            !(v % prime[j]) && (a[i - 1].s |= (1 << j - 1));
            for(;!(v % prime[j]);v /= prime[j]);
        }
        a[i - 1].w = v;
    }
    sort(a + 1,a + n);
    for(register int i = 1;i < n;++i)
    {
        if(a[i].w == 1 || (a[i].w ^ a[i - 1].w))
            memcpy(g[0],f,sizeof g[0]),memcpy(g[1],f,sizeof g[1]);
        for(register int j = full;~j;--j)
            for(register int k = full;~k;--k)
                if(!(j & k))
                    !(a[i].s & k) && (g[0][j | a[i].s][k] = (g[0][j | a[i].s][k] + g[0][j][k]) % mod),
                    !(a[i].s & j) && (g[1][j][k | a[i].s] = (g[1][j][k | a[i].s] + g[1][j][k]) % mod);
        if(a[i].w == 1 || (a[i].w ^ a[i + 1].w))
            for(register int j = full;~j;--j)
                for(register int k = full;~k;--k)
                    f[j][k] = (g[0][j][k] + g[1][j][k] - f[j][k] + mod) % mod;
    }
    for(register int i = 0;i <= full;++i)
        for(register int j = 0;j <= full;++j)
            !(i & j) && (ans = (ans + f[i][j]) % mod);
    printf("%lld\n",ans);
}