置换的排数等于其阶加一,阶是各轮换长度的 lcm。由唯一分解定理,一个可达 lcm 等价于一组互不相同的素数幂且幂和不超过 N,按素数组做有界背包计数即可。
OJ: roj
题目 ID: 1803
难度:提高+/省选-
标签:数学动态规划背包数论素数筛python
创建: 2026-10-08 04:05
更新: 2026-10-08 04:05
形式化题目
给定
对每个置换
题面样例
约定:一次变换就是整体右乘
要求的就是集合
正解
思路
第一步:把置换拆成轮换。 置换
第二步:阶 = 轮换长度的 lcm。 长度为
于是题目化为:
设
, 求 。
第三步:观察一 —— 合数轮换可以换成素数幂,只会更省。 设
第一个不等号是逐个比较:
右边取到的乘积当然也在
第四步:观察二 —— 不会重复计数。 由算术基本定理(唯一分解定理),整数
第五步:按素数组的有界背包。 每个不超过
设
小规模复核:
代码
```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
def sieve(n: int) -> list[int]:
"""筛出 [2, n] 内的素数:每个素数是一个互斥物品组(组内是不同的幂)。"""
is_comp = bytearray(n + 1)
for p in range(2, int(n ** 0.5) + 1):
if not is_comp[p]: # p 是素数,则它的倍数全是合数
is_comp[p * p :: p] = b'\x01' * len(range(p * p, n + 1, p))
return [p for p in range(2, n + 1) if not is_comp[p]]
def powers(bound: int, p: int) -> list[int]:
"""列出 p 在 [1, bound] 内的全部幂 p, p^2, ...:同组内只能选其中一个。"""
out, q = [], p
while q <= bound:
out.append(q)
q *= p
return out
def count_orders(n: int) -> int:
"""返回幂和 ≤ n 的素数幂选取方案数,即所有可能的置换阶的个数。"""
dp = [1] + [0] * n # dp[j]:选出的素数幂之和恰为 j 的方案数(空集和为 0)
for p in sieve(n):
group = powers(n, p)
nd = dp[:] # 本素数的滚动数组:先继承「不选 p」
for j, ways in enumerate(dp):
if not ways:
continue
for q in group: # 只从旧状态 dp 转移,故同一素数的两个幂不会同时被选
if j + q > n:
break
nd[j + q] += ways
dp = nd
return sum(dp) # 幂和 ≤ n 的选取都合法(不足的部分用长度 1 的轮换补齐)
def solve() -> None:
n = next(iter(map(int, sys.stdin.buffer.read().split())))
print(count_orders(n))
if __name__ == "__main__":
solve()
```cpp
```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
*/
// main.cpp:列数字(ROJ 1803)。给 1..N 的一个置换,反复写下一排直到回到 1..N,
// 排数 = 置换阶 + 1,置换阶 = 各轮换长度的 lcm,轮换长度是 N 的一个分拆(长度和 ≤ N)。
// 于是「可能的排数个数」= 分拆的 lcm 的不同取值个数。由唯一分解定理,lcm 只由各素数
// 取到的最大幂次决定,故一个可达 lcm ↔ 一组「每个素数至多取一个幂 p^a,幂和 ≤ N」的选取,
// 且不同选取给出不同乘积(无重复),答案就是这些选取的方案数,含空集(lcm=1,排数=2)。
// 算法:按素数组的有界背包计数 dp[j] = 取出的素数幂之和恰为 j 的方案数。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005; // N 的上界(题面 1 ≤ N ≤ 1000),数组多开一点防越界
typedef long long ll;
bool notPrime[MAXN]; // 埃氏筛的合数标记
int primes[MAXN]; // [2, N] 内的素数,下标 0 起
int cnt; // 素数个数
ll dp[MAXN]; // dp[j]:已处理的素数组中,选出的素数幂之和恰为 j 的方案数
ll nd[MAXN]; // 处理当前素数时的滚动数组:nd = 不选它 / 选它的某一个幂
int pw[MAXN]; // 当前素数在 [1, N] 内的所有幂 p, p^2, ... 共 k 个
int main() {
int n;
if (scanf("%d", &n) != 1) return 0;
// 埃氏筛出 [2, n] 的素数:每个素数是一个互斥物品组
for (int i = 2; i <= n; i++) {
if (notPrime[i]) continue;
primes[cnt++] = i;
for (int j = i + i; j <= n; j += i) notPrime[j] = true;
}
dp[0] = 1; // 一个素数都不选:幂和为 0,对应 lcm = 1(恒等置换,排数 2)
for (int i = 0; i < cnt; i++) {
int p = primes[i];
int k = 0;
for (ll q = p; q <= n; q *= p) pw[k++] = (int)q; // 该素数的全部合法幂
for (int j = 0; j <= n; j++) nd[j] = dp[j]; // 先继承「不选素数 p」
for (int j = 0; j <= n; j++) {
if (dp[j] == 0) continue;
for (int t = 0; t < k; t++) { // 同一素数至多选一个幂,故只看旧状态 dp
int nj = j + pw[t];
if (nj > n) break;
nd[nj] += dp[j]; // 从旧状态转移,天然避免同组内多选
}
}
for (int j = 0; j <= n; j++) dp[j] = nd[j];
}
ll ans = 0;
for (int j = 0; j <= n; j++) ans += dp[j]; // 幂和 ≤ N 的所有选取都是合法 lcm
printf("%lld\n", ans);
return 0;
}
### 复杂度
筛素数 $O(N \log\log N)$;背包部分外层 $\pi(N)$ 个素数,内层对每个素数枚举其
$O(\log_p N)$ 个幂并在容量上扫一遍,总量 $O\!\left(N \sum_{p \le N} \log_p N\right)$,
$N \le 1000$ 时约 $2 \times 10^5$ 次加法,$1 \text{ ms}$ 量级。
空间 $O(N)$(两个长度为 $N+1$ 的 64 位数组)。$N = 1000$ 时答案是
$3018714402027 < 2^{63}$,`long long` 足够(Python 自动大整数)。
## 总结
- 关键一步是把「排数」翻译成置换的阶再加一,从而把问题从"模拟"拉回到"轮换 / 分拆 / lcm"。
- 第二个关键是唯一分解定理:**lcm 的不同取值数 $=$ 素数幂选取的方案数**,省掉了全部去重。
这类「用唯一分解把"不同取值"变成"不同选择"」的转化,是计数题里很通用的一招。
- 落地是标准的**分组(有界)背包**:同组物品互斥,用「先复制旧数组、再从旧数组转移」实现。
- 注意 $N = 1$ 的边界:没有素数可筛,答案由 $dp[0]$ 给出,为 $1$(只有 $R = 2$)。
- 关于题源:本题素材目录里带 `data.py` 数据生成脚本,`data/` 的 10 个点按 $N$ 分层
($1, 2, 3, 10, 20, 100, 300, 500, 999, 1000$)自造,题面为网络重建(逐字对应
SCOI2009《游戏》/ 洛谷 P4161),出题意图与官方原题可能有偏差。标程 `std.cpp` 与本解
算法一致,且已用「枚举 $N$ 的分拆求不同 lcm 个数」的暴力在 $N \le 12$ 上逐点验证过。