寿司晚宴

GitHub跳转原题关系图返回列表

把 2..n 按大质因子分组,小质因子(恰 8 个)压成掩码做状压 DP,同组只能整组给同一人,用 g1+g2-dp 容斥合并。

OJ: roj

题目 ID: 1802

难度:提高+/省选-

标签:动态规划状态压缩数论数学python

创建: 2026-10-08 04:05

更新: 2026-10-08 04:05

形式化题目

给出 nn 与模数 pp,全集为 U={2,3,…,n}U = \{2, 3, \dots, n\}(题面的「寿司」编号为 1…n−11 \dots n-1, 美味度即 i+1i+1,正好是 2…n2 \dots n)。

求把 UU 切成两个不相交子集 AA(小 G 选的)与 BB(小 W 选的)的方案数,满足

∀x∈A,  ∀y∈B:gcd⁡(x,y)=1,\forall x \in A,\; \forall y \in B: \quad \gcd(x, y) = 1,

答案对 pp 取模。AA 与 BB 都可以为空集,但一个寿司不能同时出现在两边 (因为 x≥2x \ge 2 时 gcd⁡(x,x)=x>1\gcd(x, x) = x > 1)。

2≤n≤5002 \le n \le 500,0≤p≤1090 \le p \le 10^9(数据规模表原文如此;原 NOI 题面为 0<p≤1090 < p \le 10^9, 本目录数据取 1≤p≤1091 \le p \le 10^9)。

互质条件的质因子改写。 gcd⁡(x,y)=1\gcd(x, y) = 1 等价于「没有公共质因子」。于是设

PA=⋃x∈Apf(x),PB=⋃y∈Bpf(y),P_A = \bigcup_{x \in A} \text{pf}(x), \qquad P_B = \bigcup_{y \in B} \text{pf}(y),

条件是每一名质数最多只能被一个人占用:PA∩PB=∅P_A \cap P_B = \emptyset。 这就是全部约束,下面只讨论质因子集合。

正解

思路

朴素的状压为什么不行。 最直接的想法是让状态直接记住两人各占了哪些质数: dp[S1][S2]dp[S_1][S_2] 表示小 G 占用的质数集合为 S1S_1、小 W 为 S2S_2 的方案数,逐个寿司转移。 但 500500 以内的质数有 9595 个,2952^{95} 的状态空间直接爆炸。

根号分治打开缺口。 关键观察是:

n≤500n \le 500 时,任何 x≤500x \le 500 至多含一个大于 n≈22.36\sqrt{n} \approx 22.36 的质因子, 且该因子的指数必定为 11(因为 23×23=529>50023 \times 23 = 529 > 500)。

于是把所有质数切成两半:

  • 小质数:2,3,5,7,11,13,17,192, 3, 5, 7, 11, 13, 17, 19,共 8 个,用 28=2562^8 = 256 的掩码完全够用;
  • 大质数:2323 以上,每个 ≤500\le 500 的数里最多带一个。

把每个 x∈[2,n]x \in [2, n] 拆成 (小质因子掩码 mask, 剩下的大质因子 bigp), 其中 bigp = 1 表示这个数只由小质数构成。

大质数的绑定效应。 设 bigp = L > 1 的数有若干个(例如 L=23L = 23 对应 23,46,92,…23, 46, 92, \dots)。 它们两两共享质因子 LL,任何两个都不能分给不同人(否则两人各有一个 LL 的倍数,不互质)。 所以:

同一大质数的所有寿司,要么整组给小 G,要么整组给小 W,要么整组都不选。

而 bigp = 1 的数不含大质数,彼此不受这条约束约束,每个数各自独立成一组。

DP 形态。 全局状态只有

dp[x][y]=小 G 已用小质数集合为 x, 小 W 为 y 的方案数(x∩y=∅),dp[x][y] = \text{小 G 已用小质数集合为 } x,\ \text{小 W 为 } y \text{ 的方案数} \qquad (x \cap y = \emptyset),

初始 dp[0][0]=1dp[0][0] = 1。逐组转移:

  • 对当前组,先各复制一份 dpdp 到 g1g_1(本组只能给小 G)与 g2g_2(本组只能给小 W), 再把组内每个寿司逐个并入这两份;
  • 组内逐个并入时,g1g_1 的转移是 g1[x∣s][y]←g1[x][s]+g1[x][y]g_1[x|s][y] \gets g_1[x][s] + g_1[x][y](要求 s∩y=∅s \cap y = \emptyset), g2g_2 对称(要求 s∩x=∅s \cap x = \emptyset)。取一个数只能选一次,故枚举 x,yx, y 时倒序;
  • 合并回全局:dp′[x][y]=g1[x][y]+g2[x][y]−dp[x][y]dp'[x][y] = g_1[x][y] + g_2[x][y] - dp[x][y]。

容斥为什么是对的。 g1g_1 统计的是「本组给小 G 或都不选」,g2g_2 统计「本组给小 W 或都不选」。 两者都合法,但把「本组一个都不选」重复数了两次(g1g_1 里那次「不选」与 g2g_2 里那次「不选」 是同一个方案),所以减去一份 dp旧dp_{\text{旧}}。而「整组给 G」与「整组给 W」这两类互不重叠, 无需额外处理。

答案。 最后把所有合法状态累加:Ans=∑x∩y=∅dp[x][y] mod p\text{Ans} = \sum_{x \cap y = \emptyset} dp[x][y] \bmod p。 非法状态在转移中永远取不到值(g1g_1、g2g_2 的转移都带交集判断),所以直接遍历 0≤x,y<2560 \le x, y < 256 全部相加即可。

正确性小结。 每个合法方案被唯一地按「每个 (大质数组, 分配方式)」拆分计数, 容斥消掉重复的「不选」;每个非法方案必在第一次出现「两人各持同一质数」时被交集判断挡住。 所以答案既无重复也无遗漏。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 04:05
# update_at: 2026-10-08 04:05

import sys

SMALL = (2, 3, 5, 7, 11, 13, 17, 19)  # n<=500 时 sqrt(n)<=22,小质数恰为这 8 个

type Mask = int                # 8 位小质因子掩码(第 j 位 = 含质数 SMALL[j])
type Key = tuple[Mask, Mask]   # (小 G 掩码, 小 W 掩码),两者必无交集
type Table = dict[Key, int]    # 状态 -> 方案数(已对 p 取模)
type Item = tuple[int, Mask]   # (大质因子, 小质因子掩码),1 表示只含小质数


def split(x: int) -> Item:
    """把一个数拆成 (大质因子, 小质因子掩码);指数不影响互质性,可除干净。"""
    mask = 0
    for j, q in enumerate(SMALL):
        if x % q == 0:
            mask |= 1 << j
            while x % q == 0:
                x //= q  # 除完所有小质数,剩下的就是那个唯一的大质因子(或 1)
    return x, mask


def push(table: Table, s: Mask, to_g: bool, mod: int) -> Table:
    """把寿司 s 并入「本组只能给某一人」的表:每个状态多出「不选它」与「给它」两条去路。"""
    nxt = dict(table)  # 保留「不选」这一支
    for (x, y), v in table.items():
        if to_g:
            if s & y:
                continue  # s 与小 W 已有的质因子撞车,不能给小 G
            key = (x | s, y)
        else:
            if s & x:
                continue  # s 与小 G 已有的质因子撞车,不能给小 W
            key = (x, y | s)
        nxt[key] = (nxt.get(key, 0) + v) % mod
    return nxt


def absorb(dp: Table, group: list[Item], mod: int) -> Table:
    """整组只能给同一个人:分别算出「只给 G」「只给 W」两份表,再容斥并回全局。"""
    g1, g2 = dp, dp  # 组内逐个数累加,两份表各自从旧状态出发
    for _, s in group:
        g1 = push(g1, s, True, mod)
        g2 = push(g2, s, False, mod)
    # 「本组一个都不选」在 g1、g2 里各被数了一次,容斥时各减掉一份旧状态
    merged: Table = {}
    for key in g1.keys() | g2.keys():
        merged[key] = (g1.get(key, 0) + g2.get(key, 0) - dp.get(key, 0)) % mod
    return merged


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, mod = next(data), next(data)

    items = sorted(split(x) for x in range(2, n + 1))  # 按大质因子排序,同因子的连成一段
    dp: Table = {(0, 0): 1}
    i, cnt = 0, len(items)

    while i < cnt:
        bigp = items[i][0]
        j = i
        if bigp > 1:  # 大质因子为 1 的数各自单独成组;否则同一大质因子的整段归一组
            while j + 1 < cnt and items[j + 1][0] == bigp:
                j += 1
        dp = absorb(dp, items[i : j + 1], mod)
        i = j + 1

    print(sum(dp.values()) % mod)  # 非法状态(两掩码有交集)在转移中取不到值,直接全加


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 04:05
 * update_at: 2026-10-08 04:05
 */
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

// 小质数表:n<=500 时 sqrt(500)≈22.36,不超过 22 的质数恰好是这 8 个
static const int SP[8] = {2, 3, 5, 7, 11, 13, 17, 19};
static const int ALL = 1 << 8; // 小质数掩码空间 256

struct Item {
    int bigp; // 去掉全部小质数后剩下的部分:1 表示「只含小质数」,>1 即该数唯一的大质因子
    int mask; // 小质数因子掩码,第 j 位表示含质数 SP[j]
};
static Item item[505];

// dp[x][y]:小 G 已用的小质因子集合为 x、小 W 为 y 的方案数(保证 x&y==0)
static ll dp[ALL][ALL];
static ll g1[ALL][ALL]; // 本组只能分给小 G 时的临时数组
static ll g2[ALL][ALL]; // 本组只能分给小 W 时的临时数组

static ll n, mod;
static int cnt;

bool cmpBigp(const Item &a, const Item &b) { return a.bigp < b.bigp; }

// 把一个数拆成「小质因子掩码」+「大质因子」,大质因子为 1 时不登记
void split(int x, int &mask, int &bigp) {
    mask = 0;
    for (int j = 0; j < 8; j++) {
        if (x % SP[j] == 0) {
            mask |= 1 << j;
            while (x % SP[j] == 0) x /= SP[j]; // 指数不影响互质性,除干净再找大质因子
        }
    }
    bigp = x;
}

// 把单个寿司 s 并入「只能给小 G」的 g1 数组:x 倒序保证同一个数不会被选两次
void pushG(ll f[ALL][ALL], int s) {
    for (int x = ALL - 1; x >= 0; x--) {
        for (int y = ALL - 1; y >= 0; y--) {
            ll v = f[x][y];
            if (v == 0) continue;
            if (s & y) continue; // 会与小 W 已有的质因子冲突,不能给小 G
            ll &t = f[x | s][y];
            t = (t + v) % mod;
        }
    }
}

// 对称地并入「只能给小 W」
void pushW(ll f[ALL][ALL], int s) {
    for (int x = ALL - 1; x >= 0; x--) {
        for (int y = ALL - 1; y >= 0; y--) {
            ll v = f[x][y];
            if (v == 0) continue;
            if (s & x) continue; // 会与小 G 已有的质因子冲突,不能给小 W
            ll &t = f[x][y | s];
            t = (t + v) % mod;
        }
    }
}

void solve() {
    if (scanf("%lld %lld", &n, &mod) != 2) return;
    if (mod <= 0) { // 题面数据表写作 0<=p,p=0 取模无定义,保底输出 0
        printf("0\n");
        return;
    }

    cnt = 0;
    for (int x = 2; x <= (int)n; x++) {
        int mask, bigp;
        split(x, mask, bigp);
        item[cnt].mask = mask;
        item[cnt].bigp = bigp;
        cnt++;
    }
    sort(item, item + cnt, cmpBigp); // 排序后同一大质因子的数连成一段

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    int i = 0;
    while (i < cnt) {
        int j = i;
        while (j + 1 < cnt && item[j + 1].bigp == item[i].bigp) j++; // 当前组区间 [i, j]
        // 大质因子为 1 的数每个各自成一组(组内整组只能给一人,若不拆开就错)
        if (item[i].bigp == 1) j = i;

        memcpy(g1, dp, sizeof(dp));
        memcpy(g2, dp, sizeof(dp));
        for (int t = i; t <= j; t++) {
            // 同一大质因子的数互相不互质,整组只能给同一个人
            pushG(g1, item[t].mask);
            pushW(g2, item[t].mask);
        }
        for (int x = 0; x < ALL; x++) {
            for (int y = 0; y < ALL; y++) {
                // 「本组一个都不选」在 g1、g2 里各算了一次,容斥减去一个 dp
                ll v = (g1[x][y] + g2[x][y] - dp[x][y]) % mod;
                if (v < 0) v += mod;
                dp[x][y] = v;
            }
        }
        i = j + 1;
    }

    ll ans = 0;
    for (int x = 0; x < ALL; x++)
        for (int y = 0; y < ALL; y++)
            ans = (ans + dp[x][y]) % mod; // x&y!=0 的状态恒为 0,直接全加
    printf("%lld\n", ans);
}

int main() {
    solve();
    return 0;
}

复杂度

  • 时间:小质数只有 88 个,每轮状态对数为 38=65613^8 = 6561(每个质数有三种归属:给 G / 给 W / 都不给), 最坏 n−1=499n - 1 = 499 个寿司各扫一遍,总时间 O(n⋅38)≈3.3×106O(n \cdot 3^8) \approx 3.3 \times 10^6 次运算。 实测 n=500n = 500 时 C++ 0.08 s、Python 0.84 s(限时 2000 ms)。
  • 空间:dpdp 与两份临时数组各 256×256256 \times 256 个 ll,约 1.5 MB(限时 512 MB)。 实测 C++ 峰值 8.3 MB。
  • 与 Python 版的关系:O(n⋅38)O(n \cdot 3^8) 的算法在 Python 里同样可跑,n=500n = 500 顶格约 0.84 s, 无需降级为暴力。Python 版把状态写成 dict[(maskG, maskW)]、天然只存可达状态, 复杂度与 C++ 同阶。

总结

  • 先找「最多一个」的结构:n\sqrt{n} 分治的实质是「大质数在一个数里至多出现一次」, 这一句把 2952^{95} 压成 282^8,是本题的命门。
  • 大质数 = 绑定标记:同一大质数的数必须同归一人,把「独立选数」变成「组内背包」。
  • bigp = 1 必须逐个数各成一组:所有只含小质数的数若并成一大组,就会被误绑成 「全给同一人」,这是实现时最容易踩的坑。
  • 容斥合并 g1+g2−dpg_1 + g_2 - dp:两个「只能给某人」的表都包含「本组不选」那一支, 合并时必须减掉一次重复计数。
  • 倒序枚举保证组内不重复选用:组内逐个并入时,一维 0/1 背包的倒序技巧在这里同样适用。
  • 数据来源说明:素材源带有 data.py 生成脚本,说明本目录的 data/ 是自造的 (题面与官方 NOI2015 原题一致,但数据非官方原始数据);其中两个样例点 n=4,p=10000→21n = 4, p = 10000 \to 21 与 n=100,p=108→3107203n = 100, p = 10^8 \to 3107203 已与题面输出逐字核对通过。
  • p=0p = 0 的说明:数据规模表写作 0≤p≤1090 \le p \le 10^9,但取模 p=0p = 0 无定义; 本目录数据严格 p≥1p \ge 1,代码对 p≤0p \le 0 仅作输出 00 的保底。