把 2..n 按大质因子分组,小质因子(恰 8 个)压成掩码做状压 DP,同组只能整组给同一人,用 g1+g2-dp 容斥合并。
OJ: roj
题目 ID: 1802
难度:提高+/省选-
标签:动态规划状态压缩数论数学python
创建: 2026-10-08 04:05
更新: 2026-10-08 04:05
形式化题目
给出
求把
答案对
互质条件的质因子改写。
条件是每一名质数最多只能被一个人占用:
正解
思路
朴素的状压为什么不行。 最直接的想法是让状态直接记住两人各占了哪些质数:
根号分治打开缺口。 关键观察是:
时,任何 至多含一个大于 的质因子, 且该因子的指数必定为 (因为 )。
于是把所有质数切成两半:
- 小质数:
,共 8 个,用 的掩码完全够用; - 大质数:
以上,每个 的数里最多带一个。
把每个 (小质因子掩码 mask, 剩下的大质因子 bigp),
其中 bigp = 1 表示这个数只由小质数构成。
大质数的绑定效应。 设 bigp = L > 1 的数有若干个(例如
同一大质数的所有寿司,要么整组给小 G,要么整组给小 W,要么整组都不选。
而 bigp = 1 的数不含大质数,彼此不受这条约束约束,每个数各自独立成一组。
DP 形态。 全局状态只有
初始
- 对当前组,先各复制一份
到 (本组只能给小 G)与 (本组只能给小 W), 再把组内每个寿司逐个并入这两份; - 组内逐个并入时,
的转移是 (要求 ), 对称(要求 )。取一个数只能选一次,故枚举 时倒序; - 合并回全局:
。
容斥为什么是对的。
答案。 最后把所有合法状态累加:
正确性小结。 每个合法方案被唯一地按「每个 (大质数组, 分配方式)」拆分计数, 容斥消掉重复的「不选」;每个非法方案必在第一次出现「两人各持同一质数」时被交集判断挡住。 所以答案既无重复也无遗漏。
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:小质数只有
个,每轮状态对数为 (每个质数有三种归属:给 G / 给 W / 都不给), 最坏 个寿司各扫一遍,总时间 次运算。 实测 时 C++ 0.08 s、Python 0.84 s(限时 2000 ms)。 - 空间:
与两份临时数组各 个 ll,约 1.5 MB(限时 512 MB)。 实测 C++ 峰值 8.3 MB。 - 与 Python 版的关系:
的算法在 Python 里同样可跑, 顶格约 0.84 s, 无需降级为暴力。Python 版把状态写成 dict[(maskG, maskW)]、天然只存可达状态, 复杂度与 C++ 同阶。
总结
- 先找「最多一个」的结构:
分治的实质是「大质数在一个数里至多出现一次」, 这一句把 压成 ,是本题的命门。 - 大质数 = 绑定标记:同一大质数的数必须同归一人,把「独立选数」变成「组内背包」。
bigp = 1必须逐个数各成一组:所有只含小质数的数若并成一大组,就会被误绑成 「全给同一人」,这是实现时最容易踩的坑。- 容斥合并
:两个「只能给某人」的表都包含「本组不选」那一支, 合并时必须减掉一次重复计数。 - 倒序枚举保证组内不重复选用:组内逐个并入时,一维 0/1 背包的倒序技巧在这里同样适用。
- 数据来源说明:素材源带有
data.py生成脚本,说明本目录的data/是自造的 (题面与官方 NOI2015 原题一致,但数据非官方原始数据);其中两个样例点与 已与题面输出逐字核对通过。 的说明:数据规模表写作 ,但取模 无定义; 本目录数据严格 ,代码对 仅作输出 的保底。