JosephusTransform - 题解

标签与难度

标签: 置换群, 快速幂, 树状数组, 模拟, 约瑟夫问题 难度: 2200

题目大意喵~

主人你好呀，喵~ 这道题是这样的：

一开始，我们有一个从 1 到 $n$ 的排列 $P = \{1, 2, \dots, n\}$。 然后呢，会有 $m$ 次操作。每次操作会给你一对数字 $(k, x)$。

这个操作的意思是，我们要对当前的排列 $P$ 执行 $x$ 次“$k$-约瑟夫变换”。

那什么是“$k$-约瑟夫变换”呢？就是：

1. 把当前排列 $P$ 的所有数字看成一个环。
2. 从环的第一个数字开始，顺时针数 $k$ 个。把数到的那个数字从环里拿出来，放到一个新排列 $P'$ 的末尾。
3. 接着从刚才被移除的数字的下一个位置开始，继续在剩下的数字里数 $k$ 个，再拿出来放到 $P'$ 的末尾。
4. 重复这个过程，直到所有数字都被取出来，形成新的排列 $P'$。
5. 这个 $P'$ 就是进行了一次“$k$-约瑟夫变换”后的结果。

举个栗子！如果 $P = \{1, 2, 3, 4, 5\}$，进行一次 $k=3$ 的变换：

• 初始环: (1, 2, 3, 4, 5)。从 1 开始数 3 个，是 3。拿出 3。$P'=\{3\}$。
• 剩下环: (1, 2, 4, 5)。从 4 开始数 3 个，是 1。拿出 1。$P'=\{3, 1\}$。
• 剩下环: (2, 4, 5)。从 2 开始数 3 个，是 5。拿出 5。$P'=\{3, 1, 5\}$。
• 剩下环: (2, 4)。从 2 开始数 3 个，是 2。拿出 2。$P'=\{3, 1, 5, 2\}$。
• 剩下环: (4)。从 4 开始数 1 个，是 4。拿出 4。$P'=\{3, 1, 5, 2, 4\}$。 所以变换一次后，排列就变成了 $\{3, 1, 5, 2, 4\}$ 啦。

我们的任务就是，在所有 $m$ 次操作之后，把最终的排列打印出来。喵~

解题思路分析

这道题看起来有点复杂，特别是要变换好多次，但是别怕，我带你一步一步把它拆解开，就像拆毛线球一样简单，喵~

我们可以把整个问题分成两个核心部分：

1. 如何高效地模拟 一次 “$k$-约瑟夫变换”？
2. 如何高效地把这个变换 重复 $x$ 次？

Part 1: 高效模拟一次变换 🐾

一次变换的核心，其实就是不断地“在剩下的数字中找到第 $k$ 个”。

如果用一个普通的 std::vector 来模拟，每次找到数字后删除它，时间复杂度是 $O(N)$。因为总共有 $N$ 个数字要被移除，所以模拟一次变换的总时间就是 $O(N^2)$。对于 $N=10^5$ 的数据规模，这肯定会超时的说！就像追自己的尾巴，转了半天还在原地，喵呜~

我们需要一个更快的“爪子”来抓到第 $k$ 个数字！什么数据结构能做到呢？ 答案就是 树状数组 (Fenwick Tree) 或者 线段树 (Segment Tree)！

我们可以用一个大小为 $N$ 的树状数组，tree[i] 表示第 $i$ 个位置的数字是否还“存活”。初始时，所有位置都是 1（存活）。当一个数字被移除时，我们把对应位置的值更新为 0。

• 查询：树状数组的前缀和 query(p) 可以告诉我们从位置 1 到 $p$ 还有多少个存活的数字。
• 查找：要找“第 $k$ 个存活的数字”，我们可以通过在树状数组上进行二分查找（或者一种更快的叫做“倍增”或“二进制爬升”的技巧）来实现。这个操作的复杂度是 $O(\log N)$。

所以，模拟一次完整的 $k$-约瑟夫变换，需要进行 $N$ 次查找和 $N$ 次更新，总复杂度就是 $O(N \log N)$。这下速度就快多啦！

具体模拟过程是这样的： 我们维护一个当前指针 cursor 和剩余人数 remaining。 在第 $i$ 轮（$i$ 从 1 到 $N$）：

1. 当前剩下 remaining = N - i + 1 个人。
2. 我们需要数 steps = (k - 1) % remaining + 1 步。
3. 利用树状数组的 $O(\log N)$ 查询，找到从 cursor 开始的第 steps 个存活的位置。
4. 记录下这个位置的原始编号，然后更新树状数组，把这个位置标记为“已移除”。
5. 更新 cursor 到这个被移除的位置。

通过这个过程，我们可以得到一个置换（Permutation）。这个置换描述了元素位置的变化。比如说，我们得到了一个置换 T，其中 T[i] 表示变换后排在第 i 位的元素，在变换前是位于哪个位置的。

Part 2: 魔法时间！重复变换 $x$ 次 ✨

现在我们知道怎么做一次变换了。但题目要求做 $x$ 次，x 可能非常大，一次一次做肯定不行。

这里就要用到置换群的一点小知识啦，喵~ 一次 $k$-约瑟夫变换，本质上是对排列的位置进行了一次重排。我们可以把它看成一个作用在位置上的置换函数 $f_k$。如果原来的排列是 $P_{old}$，新的排列 $P_{new}$ 就是通过 $f_k$ 变换得到的。

做 $x$ 次变换，就相当于把这个置换函数 $f_k$ 应用 $x$ 次，也就是计算 $f_k^x$。

计算置换的幂，有两种常见的高效方法：

1. 置换快速幂：类似于整数的快速幂，只不过“乘法”操作换成了置换的“复合”操作。复合两个置换的时间是 $O(N)$，所以总时间是 $O(N \log x)$。
2. 循环分解 (Cycle Decomposition)：这是我更喜欢的方法，更优美也通常更快！任何一个置换都可以分解成若干个不相交的循环。比如置换 1->3, 3->2, 2->1 和 4->5, 5->4 就是两个循环 (1 3 2) 和 (4 5)。

一个元素在置换中只会和它所在循环里的其他元素交换位置。把置换 $f_k$ 应用 $x$ 次，就相当于让每个元素在它自己的循环里向前“走” $x$ 步。如果一个循环的长度是 $L$，那么走 $x$ 步就等价于走 $x \pmod L$ 步。

所以，我们的最终算法是：

1. 对于每个操作 $(k, x)$：
2. 生成变换置换：用 $O(N \log N)$ 的时间，通过树状数组模拟一次 $k$-约瑟夫过程，得到描述位置变化的前向置换 p。（p[i] 表示原先在位置 i 的元素，变换后去了位置 p[i]）。
3. 循环分解：用一个 visited 数组，遍历所有位置 1 到 N。如果一个位置 i 没被访问过，就从它开始，沿着 p 的指向 i -> p[i] -> p[p[i]] -> ... 走，直到回到 i，这样就找到了一个完整的循环。
4. 应用变换：对于找到的每个循环，假设其长度为 L。对于循环中的每个元素，它的新位置就是它在循环中向前平移 $x \pmod L$ 步之后的位置。我们根据这个规则，把当前排列中的值，一次性地移动到它们经过 $x$ 次变换后的最终位置。这整个过程只需要 $O(N)$。
5. 所有操作结束后，输出最终的排列。

这样，每次操作的总复杂度就是 $O(N \log N)$，完全可以接受啦！是不是很清晰了呢，喵~

代码实现

下面就是我精心为你准备的代码啦！注释写得很详细，希望能帮到你哟~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 一个可爱的树状数组模板，喵~
// T 是数据类型，默认是 int
template<typename T = int>
class FenwickTree {
private:
    int size;
    std::vector<T> tree;

    // 树状数组的核心，lowbit！
    int lowbit(int x) {
        return x & (-x);
    }

public:
    // 构造函数，初始化树状数组
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}

    // 单点更新，给 pos 位置加上 val
    void add(int pos, T val) {
        while (pos <= size) {
            tree[pos] += val;
            pos += lowbit(pos);
        }
    }

    // 查询前缀和，从 1 到 pos 的和
    T query(int pos) {
        T sum = 0;
        while (pos > 0) {
            sum += tree[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }

    // 查找第 k 个 1 的位置（也就是第 k 个存活的元素）
    // 使用倍增法，就像猫咪跳跃一样，O(logN) 哟！
    int find_kth(int k) {
        int pos = 0;
        int current_sum = 0; // 用来代替 T query(pos)
        // 从最大的 2 的幂次开始尝试跳跃
        for (int p = 1 << (std::log2(size)); p > 0; p >>= 1) {
            if (pos + p <= size && current_sum + tree[pos + p] < k) {
                pos += p;
                current_sum += tree[pos];
            }
        }
        return pos + 1;
    }
};

// 模拟一次 k-约瑟夫变换，返回一个描述位置变换的置换 p
// p[i] = j 表示原先在位置 i 的元素，变换后去了位置 j
std::vector<int> get_transform_permutation(int n, int k) {
    FenwickTree<> ft(n);
    // 初始时，所有位置都存活
    for (int i = 1; i <= n; ++i) {
        ft.add(i, 1);
    }

    std::vector<int> transform_map(n + 1);
    int current_pos = 1; // 从位置 1 开始
    for (int i = 1; i <= n; ++i) {
        int remaining_count = n - i + 1;
        int current_rank_in_ft = ft.query(current_pos - 1);
        
        // 计算需要跳过的步数
        long long steps_to_move = (k - 1) % remaining_count;
        
        // 计算目标在树状数组中的排名
        int target_rank = (current_rank_in_ft + steps_to_move) % remaining_count + 1;
        
        // 找到第 target_rank 个存活的元素
        int removed_pos = ft.find_kth(target_rank);
        
        // 记录变换关系：第 i 次被移除的元素来自 removed_pos
        transform_map[i] = removed_pos;
        
        // 将该位置标记为已移除
        ft.add(removed_pos, -1);
        current_pos = removed_pos;
    }
    
    // 我们需要的是前向置换 p[original_pos] = new_pos
    // transform_map[new_pos] = original_pos
    // 所以需要反转一下映射
    std::vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        p[transform_map[i]] = i;
    }
    return p;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    // current_perm[i] 存储的是在位置 i 上的值
    std::vector<int> current_perm(n + 1);
    std::iota(current_perm.begin() + 1, current_perm.end(), 1);

    for (int op = 0; op < m; ++op) {
        int k, x;
        std::cin >> k >> x;

        // 1. 生成变换置换
        std::vector<int> p = get_transform_permutation(n, k);

        // 2. 循环分解并应用变换
        std::vector<int> next_perm(n + 1);
        std::vector<bool> visited(n + 1, false);

        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                std::vector<int> cycle;
                int current_node = i;
                while (!visited[current_node]) {
                    visited[current_node] = true;
                    cycle.push_back(current_node);
                    current_node = p[current_node];
                }

                int cycle_len = cycle.size();
                int shift = x % cycle_len;

                for (int j = 0; j < cycle_len; ++j) {
                    int from_pos = cycle[j];
                    int to_pos = cycle[(j + shift) % cycle_len];
                    next_perm[to_pos] = current_perm[from_pos];
                }
            }
        }
        current_perm = next_perm;
    }

    // 输出最终结果
    for (int i = 1; i <= n; ++i) {
        std::cout << current_perm[i] << (i == n ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O(M \cdot N \log N)$

  • 对于 $M$ 次操作中的每一次：
  • get_transform_permutation 函数需要执行 $N$ 次循环。在循环中，ft.query 和 ft.find_kth 都是 $O(\log N)$ 的操作。所以生成一个置换的复杂度是 $O(N \log N)$。
  • 循环分解和应用变换的部分，我们需要遍历每个元素一次，所以复杂度是 $O(N)$。
  • 因此，单次操作的总复杂度是 $O(N \log N + N) = O(N \log N)$。
  • 总时间复杂度就是 $M$ 次操作乘以单次操作的复杂度，即 $O(M \cdot N \log N)$。

• 空间复杂度: $O(N)$

  • current_perm, next_perm, p 这些排列数组都需要 $O(N)$ 的空间。
  • 树状数组 ft 也需要 $O(N)$ 的空间。
  • visited 数组和 cycle 向量也都是 $O(N)$ 级别。
  • 所以总的额外空间是 $O(N)$。

知识点总结

这道题真是一次有趣的冒险，让我们学会了好多东西，喵~

1. 约瑟夫问题 (Josephus Problem): 核心是模拟一个环形出圈的过程。当数据量大时，需要高效的数据结构来优化。
2. 树状数组/线段树: 它们是解决“动态查询第k大/小元素”问题的利器。本题中，我们用树状数组来快速找到第 $k$ 个幸存者，将模拟复杂度从 $O(N^2)$ 降到了 $O(N \log N)$。
3. 置换 (Permutation): 任何对一个集合元素的重排都可以看作一个置换。理解变换的本质是一个置换，是解决问题的关键一步。
4. 置换的幂运算: 重复应用一个置换，就是计算它的幂。
5. 循环分解 (Cycle Decomposition): 这是处理置换幂运算的优雅方法。它将复杂的置换问题分解为在各个独立小圈圈里转圈圈的简单问题，大大简化了计算。

希望这篇题解能帮到你，如果还有问题，随时可以再来找我玩哦，喵~ >w<