【题解】NOI2015 寿司晚宴 分组背包 状压 dp ——quhengyi11

传送门

题意大概是选 $\{2,3,\cdots,n\}$这个集合里的两个子集使得两个自己之间的数互相互质的方案数。

首先我们来考虑 30pts 的做法。

容易发现，两个子集的数互相互质当且仅当两个子集里的质因子集合没有交集（废话

因为我们知道，当 $n\leq 30$的时候质数就有 10 个，也就是说质因子集合不会超过十个数，我们可以将它状压记为一个状态。

记 $f[s1][s2]$表示第一个质因子集合的状态为 $s1$，第二个质因子集合的状态为 $s2$

那么在加入数 $i$的时候，记 $i$所代表的质因子集合为 $s_i$，那么我们有

$$f[s1|s_i][s2] += f[s1][s2] \quad (s2 \& s_i == 0)$$
$$f[s1][s2|s_i]+=f[s1][s2] \quad (s1 \& s_i == 0)$$
表示的意义就是将 $i$给第一个集合或者第二个集合。

这样我们就有了暴力代码：

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 505
#define ls (k << 1)
#define rs (k << 1 | 1)
int n, mod, f[2][1030][1030], k, s[N], ans;
const int p[11] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int main ()
{
    scanf("%d %d", &n, &mod);
    fo (i, 2, n)
        fo (j, 1, 10)
            if (!(i % p[j]))
                s[i] |= 1 << j - 1;
    f[1][0][0] = 1;
    int up = 1023;
    fo (i, 2, n)
    {
        int now = i & 1, lst = !now;
        memcpy(f[now], f[lst], sizeof f[lst]);
        fo (s1, 0, up)
        {
            fo (s2, 0, up)
            {
                if (!f[lst][s1][s2]) continue;
                if (!(s[i] & s2))
                    f[now][s1 | s[i]][s2] = (f[now][s1 | s[i]][s2] + f[lst][s1][s2]) % mod;
                if (!(s[i] & s1))
                    f[now][s1][s2 | s[i]] = (f[now][s1][s2 | s[i]] + f[lst][s1][s2]) % mod;
            }
        }
    }
    fo (s1, 0, up)
        fo (s2, 0, up)
            ans = (ans + f[n & 1][s1][s2]) % mod;
    printf("%d\n", ans);
    return 0;
}

然而 $n\leq 500$的时候怎么搞呢？

这里我们需要用一个类似鸽巢的思想，一个小于等于 500 的数最多有一个大于等于 23 的质因子，我们可以把有这样的质因子的数单独先拎出来。

因为枚举数的顺序是无序的，我们可以先把没有这种质因子的数用上面说的方法处理完。

接下来我们就可以暴力搞搞，将最大质因子相同的数排在一起，用类似分组背包的想法，把最大质因子相同的数放在一组，一组一组地更新。

具体来讲就是开两个数组 $f1,f2$，用来表示当前这组给第一个集合或者第二个集合的方案数，当换到下一组的时候，我们这样更新 $f$数组
$$f[s1][s2] = f1[s1][s2] + f2[s1][s2] – f[s1][s2]$$
因为这一组不选在 $f1,f2$里面被算了两次，所以要减去不选的情况。

复杂度 $O(n2^{16})$

代码：

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 505
#define ls (k << 1)
#define rs (k << 1 | 1)
#define M 260
ll n, mod, f[M][M], k, s[N], ans, f1[M][M], f2[M][M];
const int p[9] = {0, 2, 3, 5, 7, 11, 13, 17, 19};
struct node{
    int b, s;
    friend bool operator < (node x, node y)
    {
        return x.b < y.b;
    }
}t[N];
int main ()
{
    scanf("%lld %lld", &n, &mod);
    fo (i, 2, n)
    {
        t[i].b = i;
        fo (j, 1, 8)
        {
            if (!(i % p[j]))
            {
                t[i].s |= 1 << j - 1;
                t[i].b /= p[j];
                while (!(t[i].b % p[j])) t[i].b /= p[j];
            }
        }
    }
    f[0][0] = 1;
    std::sort(t + 2, t + n + 1);
    int up = 255, pos = 2;
    while (t[pos].b == 1) ++pos; --pos;
    fo (i, 2, pos)
    {
        fd (s1, up, 0)
        {
            fd (s2, up, 0)
            {
                if (!f[s1][s2]) continue;
                if (!(s2 & t[i].s))
                    f[s1 | t[i].s][s2] += f[s1][s2];
                if (!(s1 & t[i].s))
                    f[s1][s2 | t[i].s] += f[s1][s2];
            }
        }
        fo (s1, 0, up)
            fo (s2, 0, up)
                if (f[s1][s2] > mod) f[s1][s2] %= mod;
    }
    fo (i, pos + 1, n)
    {
        if (t[i].b != t[i - 1].b)
        {
            memcpy(f1, f, sizeof f);
            memcpy(f2, f, sizeof f);
        }
        fd (s1, up, 0)
        {
            fd (s2, up, 0)
            {
                if (!(s2 & t[i].s))
                    f1[s1 | t[i].s][s2] += f1[s1][s2];
                if (!(s1 & t[i].s))
                    f2[s1][s2 | t[i].s] += f2[s1][s2];
                if (f1[s1 | t[i].s][s2] > mod) f1[s1 | t[i].s][s2] %= mod;
                if (f2[s1][s2 | t[i].s] > mod) f2[s1][s2 | t[i].s] %= mod;
            }
        }
        if (t[i].b != t[i + 1].b || i == n)
        {
            fo (s1, 0, up)
                fo (s2, 0, up)
                    f[s1][s2] = (f1[s1][s2] + f2[s1][s2] - f[s1][s2] + mod) % mod;
        }
    }
    fo (s1, 0, up)
        fo (s2, 0, up)
            ans = (ans + f[s1][s2]) % mod;
    printf("%lld\n", (ans + mod) % mod);
    return 0;
}