洛谷P2150 [NOI2015] 寿司晚宴题解

题目链接：P2150 [NOI2015] 寿司晚宴

题意：

为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。

在晚宴上，主办方为大家提供了 $n−1$ 种不同的寿司，编号 $1,2,3,\ldots,n-1$，其中第 $i$ 种寿司的美味度为 $i+1$。（即寿司的美味度为从 $2$ 到 $n$）

现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 $x$ 的寿司，小 W 品尝的寿司中存在一种美味度为 $y$ 的寿司，而 $x$ 与 $y$ 不互质。

现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 $p$ 取模）。

注意一个人可以不吃任何寿司。

省流：

令两个集合为 $\{2,3,\cdots,n\}$ 的子集，要求两个集合的元素必须两两互质，求方案数。

输入格式：

输入文件的第 $1$ 行包含 $2$ 个正整数 $n, p$ 中间用单个空格隔开，表示共有 $n$ 种寿司，最终和谐的方案数要对 $p$ 取模。

输出格式：

输出一行包含 $1$ 个整数，表示所求的方案模 $p$ 的结果。

数据范围：

$2 \le n \le 500,~1 \le p \le 10^9$ 。

首先可以发现，一个方案和谐当且仅当两个集合包含的质数没有交集。

注意到 $500$ 以内的数最多只有一个比 $22$ 大的质因子

那么只需要记录这个质因子就好状压了，因为剩下最多有 $8$ 个质因子

设 $f(S_1,S_2)$ 为两个集合分别吃了状态 $S_1,S_2$ 对应的寿司时的方案数

枚举 $i$ 并考察它落在了哪个集合里，这里需要临时记录个 $f_1,f_2$ 来转移，详见代码。

时间复杂度 $\mathcal{O}(2^{16}n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int p[]={0,2,3,5,7,11,13,17,19}; int mod;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(555))
#define M ((int)(333))

int dp[M][M], f1[M][M], f2[M][M];
struct node
{
    int v, mx, S;
    node() = default;
    node(int val)
    {
        int tmp = v = val; mx = -1, S = 0;
        for(int i = 1; i <= 8; i++)
            if(tmp % p[i] == 0)
            {
                S |= (1 << (i - 1));
                while(tmp % p[i] == 0) tmp /= p[i];
            }
        if(tmp > 1) mx = tmp;
    }
}a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n >> mod; dp[0][0] = 1;
    for(int i = 2; i <= n; i++) a[i - 1] = node(i);
    sort(a + 1, a + 1 + n, [](node a, node b) { return a.mx < b.mx; });
    for(int i = 1; i < n; i++)
    {
        if(i == 1 || a[i].mx != a[i - 1].mx || a[i].mx == -1) {
            memcpy(f1, dp, sizeof(f1)); memcpy(f2, dp, sizeof(f2));
        }
        for(int j = 255; ~j; j--)
            for(int k = 255; ~k; k--) if(!(j & k)) {
                if(!(a[i].S & j)) add(f2[j][k | a[i].S], f2[j][k]);
                if(!(a[i].S & k)) add(f1[j | a[i].S][k], f1[j][k]);
            }
        if(i == n - 1 || a[i].mx != a[i + 1].mx || a[i].mx == -1)
        {
            for(int j = 0; j <= 255; j++)
                for(int k = 0; k <= 255; k++) if(!(j & k)) {
                    dp[j][k] = (f1[j][k] + f2[j][k] + mod - dp[j][k]) % mod;
                }
        }
    }
    int res = 0;
    for(int j = 0; j <= 255; j++)
        for(int k = 0; k <= 255; k++)
            if(!(j & k) && dp[j][k]) add(res, dp[j][k]);
    cout << res << '\n';
    return 0;
}