列数字

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

置换的排数等于其阶加一,阶是各轮换长度的 lcm。由唯一分解定理,一个可达 lcm 等价于一组互不相同的素数幂且幂和不超过 N,按素数组做有界背包计数即可。

OJ: roj

题目 ID: 1803

难度:提高+/省选-

标签:数学动态规划背包数论素数筛python

创建: 2026-10-08 04:05

更新: 2026-10-08 04:05

形式化题目

给定 NN,考虑所有满足「每个数 i∈[1,N]i \in [1,N] 都有唯一且互不相同的像 f(i)∈[1,N]f(i) \in [1,N]」的 对应关系 ff,也就是 1∼N1 \sim N 上的全体置换。

对每个置换 ff,从第一排 1,2,…,N1, 2, \ldots, N 出发,反复在下面写出当前排的像,直到再次出现 1,2,…,N1, 2, \ldots, N,记写下的总排数(含最初的 1,2,…,N1,2,\dots,N 和最后重新出现的 1,2,…,N1,2,\dots,N)为 R(f)R(f)。 问:R(f)R(f) 在所有置换上一共有多少种不同的取值?

题面样例 N=6N = 6 的对应关系是 1→2, 2→3, 3→1, 4→5, 5→4, 6→61 \to 2,\ 2 \to 3,\ 3 \to 1,\ 4 \to 5,\ 5 \to 4,\ 6 \to 6, 共写下 7 排,即 R=7R = 7。

约定:一次变换就是整体右乘 ff,所以第 k+1k+1 排是 fkf^k(作用在 1..N1..N 上)。 最小正整数 kk 使 fk=idf^k = \mathrm{id} 记作置换的阶 ord⁡(f)\operatorname{ord}(f), 则第 1+ord⁡(f)1 + \operatorname{ord}(f) 排第一次回到初始排,即

R(f)=ord⁡(f)+1.R(f) = \operatorname{ord}(f) + 1.

要求的就是集合 { R(f):f∈SN }\{\,R(f) : f \in S_N\,\} 的大小,由上式它等于 { ord⁡(f) }\{\,\operatorname{ord}(f)\,\} 的大小。数据范围 1≤N≤10001 \le N \le 1000。

正解

思路

第一步:把置换拆成轮换。 置换 ff 唯一分解为若干个互不相交的轮换,设它们的长度为 c1,c2,…,ck≥1c_1, c_2, \ldots, c_k \ge 1。这些长度之和恰好是 NN(长度 11 的轮换就是不动点), 所以 (c1,…,ck)(c_1, \dots, c_k) 遍历的正是 NN 的全部整数分拆。

第二步:阶 = 轮换长度的 lcm。 长度为 cc 的轮换每 cc 步归位一次,各轮换互不干扰, 所以 ft=id  ⟺  ci∣t (∀i)f^t = \mathrm{id} \iff c_i \mid t\ (\forall i),最小正解就是

ord⁡(f)=lcm⁡(c1,c2,…,ck).\operatorname{ord}(f) = \operatorname{lcm}(c_1, c_2, \ldots, c_k).

于是题目化为:

设 LN={ lcm⁡(λ):λ 是 N 的分拆 }\mathcal{L}_N = \{\, \operatorname{lcm}(\lambda) : \lambda \text{ 是 } N \text{ 的分拆} \,\}, 求 ∣LN∣|\mathcal{L}_N|。

第三步:观察一 —— 合数轮换可以换成素数幂,只会更省。 设 L∈LNL \in \mathcal{L}_N 由分拆 λ\lambda 产生,写成 L=p1a1p2a2⋯pmamL = p_1^{a_1} p_2^{a_2} \cdots p_m^{a_m}(pip_i 互不相同,ai≥1a_i \ge 1)。 要造出乘积恰为 LL 的 lcm,最省长度的选法就是直接拿这些素数幂当轮换长度:

∑i=1mpiai  ≤  ∏i=1mpiai  =  L  ≤  ∑jcj  =  N.\sum_{i=1}^{m} p_i^{a_i} \;\le\; \prod_{i=1}^{m} p_i^{a_i} \;=\; L \;\le\; \sum_{j} c_j \;=\; N .

第一个不等号是逐个比较:pa≤pap^a \le p a 对 p≥2,a≥1p \ge 2, a \ge 1 成立, 更直接地,把任意合数 c=uvc = uv(u,v>1u, v > 1)换成长度 uu 与 vv 两个轮换, lcm 不变(uvuv 与 lcm(u,v)\mathrm{lcm}(u,v) 的素因子幂次相同)而总长度从 uvuv 降到 u+v≤uvu + v \le uv, 反复替换即得「轮换长度全取成互不相同的素数幂」且总长不增。所以

L∈LN  ⟺  ∃ {p1a1,…,pmam} 两两素因子不同,∑ipiai≤N.L \in \mathcal{L}_N \iff \exists\, \{p_1^{a_1}, \ldots, p_m^{a_m}\} \text{ 两两素因子不同},\quad \sum_i p_i^{a_i} \le N .

右边取到的乘积当然也在 LN\mathcal{L}_N 里(剩下的 N−∑piaiN - \sum p_i^{a_i} 个位置用长度 11 的轮换补齐, 不动点不影响 lcm),两边互为充要。

第四步:观察二 —— 不会重复计数。 由算术基本定理(唯一分解定理),整数 LL 的素因子分解唯一。 不同的「素数幂集合」(集合内幂的底数两两不同)给出不同的素因子与指数,因此乘积不同。 不需要哈希集合去重:答案就是上面那种选取的方案数本身。

第五步:按素数组的有界背包。 每个不超过 NN 的素数 pp 是一个物品组,组内物品是 它各个幂 p,p2,…≤Np, p^2, \ldots \le N(体积 == 数值),每组至多选一个(同一素数只能贡献一个 最高次幂)。容量 NN,求装入体积 ≤N\le N 的方案数——含「一件都不装」这一种, 它对应恒等置换(L=1L = 1,排数 R=2R = 2)。

设 dp[j]dp[j] 为已处理若干素数组后、所选素数幂之和恰为 jj 的方案数,初始 dp[0]=1dp[0] = 1。 处理素数 pp 时把旧状态整体继承到 ndnd(表示不选 pp),再让旧 dpdp 向 nd[j+pt]nd[j + p^t] 累加(表示选它的某一个幂)。由于转移的源端是旧数组,同一素数的两个幂 不可能在本轮同时被用上,分组互斥自动成立。答案 ∑j=0Ndp[j]\sum_{j=0}^{N} dp[j]。

小规模复核:N=6N = 6 时可选素数幂有 2,4,3,52, 4, 3, 5(4=224 = 2^2 与 22 同组)与空集, 共 1+4+(合法二元素组合 {2,3},{4,3}?→4+3=7>6 不行)1 + 4 + (\text{合法二元素组合 } \{2,3\}, \{4,3\}? \to 4+3=7>6 \text{ 不行}), 实际方案为 {},{2},{4},{3},{5},{2,3}\{\},\{2\},\{4\},\{3\},\{5\},\{2,3\} 共 6 种,即 L∈{1,2,4,3,5,6}L \in \{1,2,4,3,5,6\}, R∈{2,3,5,4,6,7}R \in \{2,3,5,4,6,7\},与「含合数轮换能造出 L=6L = 6」相符。

代码

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


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()
text

```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;
}
text

### 复杂度

筛素数 $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$ 上逐点验证过。