托康展开+约瑟夫环#

[算法思想]#

康托展开的核心思想是利用阶乘数系将排列的字典序排名与排列本身建立一一对应的双射关系。其原理是按位统计“当前位之后尚未使用的元素中，比当前元素小的个数”，并将该计数乘以剩余元素个数的阶乘，最后将各结果累加，从而得到该排列在所有全排列中的唯一字典序序位（通常加 1 转为 1-based 排名）。这一思想同样支持逆向操作，能够根据排名反推出原始排列，常用于状态压缩、哈希去重及解决排列的计数与定位问题。

托康展开原理#

康托展开是一个双射，它将一个排列映射为一个整数，该整数表示该排列在所有排列中的字典序排名（从 0 开始）。

\text{rank} \in [0, N! - 1]

对于一个排列 $X = (X_1, X_2, \dots, X_N)$ ：

\text{rank}(X) = \sum_{i=1}^{N} a_i \times (N - i)!

其中 $a_i$ = 在 X[i] 后面出现的、比 X[i] 小的数的个数。

等价于：在当前未使用的数字中，有多少个比 X[i] 小的数。

这个查询可以通过树状数组进行查询

1
def cantor_rank(X):
2
    N = len(X)
3
    fact = [1] * (N + 1)
4
    for i in range(1, N + 1):
5
        fact[i] = fact[i-1] * i
6

7
    rank = 0
8
    used = [False] * (N + 1)
9

10
    for i in range(N):
11
        # 统计未使用且小于 X[i] 的数字个数
12
        cnt = 0
13
        for num in range(1, X[i]):
14
            if not used[num]:
15
                cnt += 1
16

17
        rank += cnt * fact[N - i - 1]
18
        used[X[i]] = True
19

20
    return rank

把排列看作一个 N 位数字，每位可以选剩余未用的数字：

1
第1位：有 N 种选择 → rank 变化量 = 选第 k 小的数，跳过 (k-1) × (N-1)! 个排列
2
第2位：有 N-1 种选择 → rank 变化量 = 选第 k 小的数，跳过 (k-1) × (N-2)! 个排列
3
...

本质：康托展开就是计算”有多少个排列排在它前面”。

逆康托展开#

给定 rank，还原排列：

1
def cantor_inverse(N, rank):
2
    fact = [1] * (N + 1)
3
    for i in range(1, N + 1):
4
        fact[i] = fact[i-1] * i
5

6
    available = list(range(1, N + 1))
7
    res = []
8

9
    for i in range(N):
10
        idx = rank // fact[N - i - 1]
11
        rank %= fact[N - i - 1]
12
        res.append(available.pop(idx))
13

14
    return res

[托康展开]#

洛谷P5367#

题目#

求 $1\sim N$ 的一个给定全排列在所有 $1\sim N$ 全排列中的排名。结果对 $998244353$ 取模。

树状数组+托康展开#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int MOD = 998244353;
4
class Fenwick {
5
private:
6
    int n;
7
    vector<int> bit;
8
public:
9
    Fenwick(int n) : n(n), bit(n + 1, 0) {}
10

11
    void add(int idx, int val) {
12
        while (idx <= n) {
13
            bit[idx] = (bit[idx] + val) % MOD;
14
            idx += idx & -idx;
15
        }
16
    }
17

18
    int sum(int idx) {
19
        int res = 0;
20
        while (idx > 0) {
21
            res = (res + bit[idx]) % MOD;
22
            idx -= idx & -idx;
23
        }
24
        return res;
25
    }
26
};
27

28
int tuo_kang(vector<int>& a) {
29
    int n = a.size();
30
    vector<long long> fact(n + 1, 1);
31
    for (int i = 1; i <= n; i++) {
32
        fact[i] = fact[i - 1] * i % MOD;
33
    }
34
    Fenwick bit(n);
35
    for (int i = 1; i <= n; i++) {
36
        bit.add(i, 1);
37
    }
38
    long long rank = 0;
39
    for (int i = 0; i < n; i++) {
40
        int cnt = bit.sum(a[i] - 1);
41
        rank = (rank + cnt * fact[n - i - 1]) % MOD;
42
        bit.add(a[i], -1);
43
    }
44
    return (rank + 1) % MOD;
45
}
46
int main() {
47
    ios::sync_with_stdio(false);
48
    cin.tie(nullptr);
49
    int n;
50
    cin >> n;
51
    vector<int> a(n);
52
    for (int i = 0; i < n; i++) {
53
        cin >> a[i];
54
    }
55
    cout << tuo_kang(a) << '\n';
56
    return 0;
57
}

1
MOD = 998244353
2
class Fenwick:
3
    def __init__(self, n):
4
        self.n = n
5
        self.bit = [0] * (n + 1)
6

7
    def add(self, idx, val):
8
        while idx <= self.n:
9
            self.bit[idx] += val
10
            idx += idx & -idx
11

12
    def sum(self, idx):
13
        res = 0
14
        while idx > 0:
15
            res += self.bit[idx]
16
            idx -= idx & -idx
17
        return res
18

19
def tuo_kang(a):
20
    n = len(a)
21
    fact = [1] * (n + 1)
22
    for i in range(1, n + 1):
23
        fact[i] = fact[i - 1] * i % MOD
24

25
    bit = Fenwick(n)
26
    for i in range(1, n + 1):
27
        bit.add(i, 1)
28
    rank = 0
29

30
    for i in range(n):
31
        cnt = bit.sum(a[i] - 1)
32
        rank = (rank + cnt * fact[n - i - 1]) % MOD
33
        bit.add(a[i], -1)
34
    return (rank + 1) % MOD
35

36
def main():
37
    n = int(input())
38
    a = list(map(int,input().split()))
39
    print(tuo_kang(a))
40

41
if __name__ == "__main__":
42
    main()

ABC468C-DFS/康托展开#

题目#

给你一个整数 $N$ 和整数序列 $P=(P_1,P_2,\ldots, P_N)$ 和 $Q=(Q_1,Q_2,\ldots,Q_N)$ ，每个序列都是 $(1,2,\ldots,N)$ 的排列。

请问有多少个整数序列是 $(1,2,\ldots,N)$ 的置换序列，且其序数大于 $P$ ，小于 $Q$ 。

什么是整数序列的词序？

对于整数序列 $S = (S_1,S_2,\ldots,S_{|S|})$ 和 $T = (T_1,T_2,\ldots,T_{|T|})$ ，如果下面的 $1.$ 或 $2.$ 成立，我们就说 $S$ 在词典上小于 $T$ 。这里， $|S|, |T|$ 分别表示 $S, T$ 的长度。

$|S| \lt |T|$ 和 $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$ 。
存在一个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ $1 \leq i \leq min {∣ S ∣, ∣ T ∣}$ ，使得以下两个条件都成立。
- $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$
- $S_i$ 在数值上小于 $T_i$ 。

DFS#

排列型DFS

1
def dfs(n, p, q):
2
    used = [False] * (n + 1)
3
    ans = 0
4
    def dfs(pos, cur):
5
        nonlocal ans
6
        if pos == n:
7
            if p < cur < q:
8
                ans += 1
9
            return
10
        for num in range(1, n + 1):
11
            if not used[num]:
12
                if cur and cur < p[:pos] and cur > q[:pos]:
13
                    continue
14
                used[num] = True
15
                cur.append(num)
16
                dfs(pos + 1, cur)
17
                cur.pop()
18
                used[num] = False
19

20
    dfs(0, [])
21
    return ans
22
n = int(input())
23
p = list(map(int,input().split()))
24
q = list(map(int,input().split()))
25
print(dfs(n,p,q))

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int dfs(int n, vector<int>& p, vector<int>& q) {
5
    vector<bool> used(n + 1, false);
6
    int ans = 0;
7

8
    function<void(int, vector<int>&)> dfs_impl = [&](int pos, vector<int>& cur) {
9
        if (pos == n) {
10
            if (cur > p && cur < q) {
11
                ans++;
12
            }
13
            return;
14
        }
15
        for (int num = 1; num <= n; num++) {
16
            if (!used[num]) {
17
                // 剪枝：如果前缀已经不可能在区间内
18
                bool prefix_ok = true;
19
                if (pos > 0) {
20
                    bool less_than_p = true, greater_than_q = true;
21
                    for (int k = 0; k < pos; k++) {
22
                        if (cur[k] >= p[k]) less_than_p = false;
23
                        if (cur[k] <= q[k]) greater_than_q = false;
24
                    }
25
                    if (less_than_p && greater_than_q) {
26
                        prefix_ok = false;
27
                    }
28
                }
29
                if (!prefix_ok) continue;
30

31
                used[num] = true;
32
                cur.push_back(num);
33
                dfs_impl(pos + 1, cur);
34
                cur.pop_back();
35
                used[num] = false;
36
            }
37
        }
38
    };
39

40
    vector<int> cur;
41
    dfs_impl(0, cur);
42
    return ans;
43
}
44

45
int main() {
46
    int n;
47
    cin >> n;
48
    vector<int> p(n), q(n);
49
    for (int i = 0; i < n; i++) cin >> p[i];
50
    for (int i = 0; i < n; i++) cin >> q[i];
51

52
    cout << dfs(n, p, q) << endl;
53
    return 0;
54
}

库函数#

使用permutations直接生成全排列

1
from itertools import permutations
2
n = int(input())
3
p = list(map(int, input().split()))
4
q = list(map(int, input().split()))
5
ans = 0
6
for a in permutations([i + 1 for i in range(n)]):
7
    ans += p < list(a) < q
8
print(ans)

康托展开#

1
MOD = 998244353
2
class Fenwick:
3
    def __init__(self, n):
4
        self.n = n
5
        self.bit = [0] * (n + 1)
6

7
    def add(self, idx, val):
8
        while idx <= self.n:
9
            self.bit[idx] += val
10
            idx += idx & -idx
11

12
    def sum(self, idx):
13
        res = 0
14
        while idx > 0:
15
            res += self.bit[idx]
16
            idx -= idx & -idx
17
        return res
18
def tuo_kang(a):
19
    n = len(a)
20
    fact = [1] * (n + 1)
21
    for i in range(1, n + 1):
22
        fact[i] = fact[i - 1] * i % MOD
23
    bit = Fenwick(n)
24
    for i in range(1, n + 1):
25
        bit.add(i, 1)
26
    rank = 0
27
    for i in range(n):
28
        cnt = bit.sum(a[i] - 1)  # 未使用且小于 a[i] 的个数
29
        rank = (rank + cnt * fact[n - i - 1]) % MOD
30
        bit.add(a[i], -1)  # 标记 a[i] 已使用
31
    return (rank + 1) % MOD
32
def main():
33
    n = int(input())
34
    a = list(map(int,input().split()))
35
    b = list(map(int,input().split()))
36
    print(tuo_kang(b) - tuo_kang(a) - 1 if tuo_kang(b) - tuo_kang(a) - 1 > 0 else 0)
37
if __name__ == "__main__":
38
    main()

[逆托康展开]#

逆康托展开：已知 rank，从高位到低位依次还原 cnt_i，然后从未使用的数字中选出第 cnt_i + 1 小的数字。

核心要点在于用阶乘进制表示排列

对于给定的一个排名rank

从高位到低位逐位确定：

对于位置 i（0-based）：

fact = fact[n - 1 - i]（剩余位置数的阶乘）
idx = rank // fact（当前位选择的数字在 nums 中的下标）
ans[i] = nums[idx]
从 nums 中删除 nums[idx]
rank %= fact

1
n = 5, rank = 3 (0-based)
2
fact = [1, 1, 2, 6, 24, 120]
3
nums = [1, 2, 3, 4, 5]
4

5
i=0: fact = 4! = 24, idx = 3//24 = 0, ans[0]=nums[0]=1, nums=[2,3,4,5], rank=3
6
i=1: fact = 3! = 6, idx = 3//6 = 0, ans[1]=nums[0]=2, nums=[3,4,5], rank=3
7
i=2: fact = 2! = 2, idx = 3//2 = 1, ans[2]=nums[1]=4, nums=[3,5], rank=1
8
i=3: fact = 1! = 1, idx = 1//1 = 1, ans[3]=nums[1]=5, nums=[3], rank=0
9
i=4: fact = 0! = 1, idx = 0//1 = 0, ans[4]=nums[0]=3, nums=[]
10

11
结果: [1, 2, 4, 5, 3]

如何快速找到第idx+1小的数字？

1
# 维护一个树状数组，初始所有位置为 1
2
def find_kth(k):  # 找第 k 小的未使用数字（1-based）
3
    l, r = 1, n
4
    while l < r:
5
        mid = (l + r) // 2
6
        if bit.sum(mid) >= k:
7
            r = mid
8
        else:
9
            l = mid + 1
10
    return l

洛谷U72177#

逆托康展开#

1
import sys
2

3
class Fenwick:
4
    def __init__(self, n):
5
        self.n = n
6
        self.bit = [0] * (n + 1)
7

8
    def add(self, idx, val):
9
        while idx <= self.n:
10
            self.bit[idx] += val
11
            idx += idx & -idx
12

13
    def sum(self, idx):
14
        res = 0
15
        while idx > 0:
16
            res += self.bit[idx]
17
            idx -= idx & -idx
18
        return res
19

20

21
def get_fact(n):
22
    """预处理阶乘数组"""
23
    fact = [1] * (n + 1)
24
    for i in range(1, n + 1):
25
        fact[i] = fact[i - 1] * i
26
    return fact
27

28

29
def cantor(a, fact):
30
    """
31
    康托展开：求排列的排名（0-based）
32
    a: 1..n 的排列
33
    fact: 阶乘数组
34
    返回: 0-based 排名
35
    """
36
    n = len(a)
37
    bit = Fenwick(n)
38
    for i in range(1, n + 1):
39
        bit.add(i, 1)
40

41
    rank = 0
42
    for i, x in enumerate(a):
43
        cnt = bit.sum(x - 1)  # 比 x 小的未使用元素个数
44
        rank += cnt * fact[n - i - 1]
45
        bit.add(x, -1)
46
    return rank
47

48

49
def inv_cantor(n, rank, fact):
50
    """
51
    逆康托展开：根据排名还原排列
52
    n: 排列长度
53
    rank: 0-based 排名
54
    fact: 阶乘数组
55
    返回: 排列列表
56
    """
57
    bit = Fenwick(n)
58
    for i in range(1, n + 1):
59
        bit.add(i, 1)
60

61
    ans = []
62
    for i in range(n):
63
        k = rank // fact[n - i - 1] + 1  # 第 k 小（1-based）
64
        rank %= fact[n - i - 1]
65

66
        # 二分查找第 k 小的未使用数字
67
        l, r = 0, n + 1
68
        while l + 1 < r:
69
            mid = (l + r) // 2
70
            if bit.sum(mid) >= k:
71
                r = mid
72
            else:
73
                l = mid
74
        ans.append(r)
75
        bit.add(r, -1)
76

77
    return ans
78

79

80
def solve():
81
    input = sys.stdin.readline
82

83
    n = int(input())
84
    m = int(input())
85
    a = list(map(int, input().split()))
86

87
    # 预处理阶乘
88
    fact = get_fact(n)
89

90
    # 康托展开求当前排名
91
    rank = cantor(a, fact)
92

93
    # 加上 M
94
    new_rank = rank + m
95

96
    # 逆康托展开还原排列
97
    ans = inv_cantor(n, new_rank, fact)
98

99
    print(' '.join(map(str, ans)))
100

101

102
if __name__ == "__main__":
103
    solve()

CF501D#

题目#

人话：

给定两个排列p和q，求出这两个排列的排名和，之后求出这个排名的排列

逆托康展开#

1
import sys
2

3
class Fenwick:
4
    def __init__(self, n):
5
        self.n = n
6
        self.bit = [0] * (n + 1)
7

8
    def add(self, idx, val):
9
        while idx <= self.n:
10
            self.bit[idx] += val
11
            idx += idx & -idx
12

13
    def sum(self, idx):
14
        res = 0
15
        while idx > 0:
16
            res += self.bit[idx]
17
            idx -= idx & -idx
18
        return res
19

20
    def kth(self, k):
21
        """返回第 k 小的未使用数字（1-based）"""
22
        l, r = 0, self.n
23
        while l + 1 < r:
24
            mid = (l + r) // 2
25
            if self.sum(mid) >= k:
26
                r = mid
27
            else:
28
                l = mid
29
        return r
30

31

32
def get_coeff(perm):
33
    """
34
    将排列转换为阶乘数制系数数组
35
    coeff[i] = 在第 i 位，比 perm[i] 小且未使用的数字个数
36
    """
37
    n = len(perm)
38
    bit = Fenwick(n)
39
    for i in range(1, n + 1):
40
        bit.add(i, 1)
41

42
    coeff = [0] * n
43
    for i, x in enumerate(perm):
44
        coeff[i] = bit.sum(x)  # 注意：x 是 0-based，所以比 x 小的个数 = sum(x)
45
        bit.add(x + 1, -1)    # 删除 x
46
    return coeff
47

48

49
def recover_perm(coeff):
50
    """
51
    从阶乘数制系数数组还原排列
52
    """
53
    n = len(coeff)
54
    bit = Fenwick(n)
55
    for i in range(1, n + 1):
56
        bit.add(i, 1)
57

58
    ans = [0] * n
59
    for i, c in enumerate(coeff):
60
        k = c + 1  # 第 k 小（1-based）
61
        num = bit.kth(k)
62
        ans[i] = num - 1
63
        bit.add(num, -1)
64
    return ans
65

66

67
def solve():
68
    input = sys.stdin.readline
69

70
    n = int(input())
71
    p = list(map(int, input().split()))
72
    q = list(map(int, input().split()))
73

74
    cp = get_coeff(p)
75
    cq = get_coeff(q)
76

77
    # 阶乘数制相加（从低位到高位）
78
    res = [0] * n
79
    carry = 0
80
    for i in range(n - 1, -1, -1):
81
        base = n - i  # 当前位的进制：从 1 到 n
82
        s = cp[i] + cq[i] + carry
83
        res[i] = s % base
84
        carry = s // base
85
    # carry 忽略（模 n!）
86

87
    ans = recover_perm(res)
88
    print(' '.join(map(str, ans)))
89

90

91
if __name__ == "__main__":
92
    solve()

[约瑟夫环]#

n 个人的编号是 1∼n，如果他们依编号按顺时针排成一个圆圈，从编号是 1 的人开始顺时针报数。

（报数是从 1 报起）当报到 k 的时候，这个人就退出游戏圈。下一个人重新从 1 开始报数。

求最后剩下的人的编号。这就是著名的约瑟夫环问题。

本题目就是已知 n，k 的情况下，求最后剩下的人的编号。

每次出队一人，在约瑟夫环上的每个人都向前移动了 $k$ 位。那么如果要反着来，就是每次加上一个人，在约瑟夫环上的每个人都向后移动了 $k$ 位。易得剩下一个人的时候，最终答案对应的下标为 $F(1)=0$ 。那么加上一个人，最终答案对应的下标就是 $F(2)=(F(1)+k)mod2$ 。再加上一个人，最终答案对应的下标就是 $F(3)=(F(2)+k)mod3$ 。以此类推，那么可以得出递推公式：

$F(1)=0$
$F(n)=(F(n−1)+k)modn$ 于是就可以求答案了。

1
def josephus(n, k):
2
    ans = 0  # f(1, k) = 0
3
    for i in range(2, n + 1):
4
        ans = (ans + k) % i
5
    return ans
6

7
def main():
8
    n,k = map(int,input().split())
9
    print(josephus(n,k) + 1)
10

11
if __name__ == "__main__":
12
    main()

音乐

音乐

托康展开+约瑟夫环#

[算法思想]#

托康展开原理#

逆康托展开#

[托康展开]#

洛谷P5367#

题目#

树状数组+托康展开#

ABC468C-DFS/康托展开#

题目#

DFS#

库函数#

康托展开#

[逆托康展开]#

洛谷U72177#

逆托康展开#

CF501D#

题目#

逆托康展开#

[约瑟夫环]#

文章分享

音乐

目录

音乐

音乐

[算法专项] 托康展开+约瑟夫环

托康展开+约瑟夫环#

[算法思想]#

托康展开原理#

逆康托展开#

[托康展开]#

洛谷P5367#

题目#

树状数组+托康展开#

ABC468C-DFS/康托展开#

题目#

DFS#

库函数#

康托展开#

[逆托康展开]#

洛谷U72177#

逆托康展开#

CF501D#

题目#

逆托康展开#

[约瑟夫环]#

文章分享

音乐

目录