POJ 1721 CARDS：置換群週期性求原始序列

題目大意

給定置換後的序列（第 s 次置換後），求原始序列。置換規則：位置 i 的元素移動到位置 a[i]。

核心洞察：置換群的循環節

• 置換操作構成群，存在最小正整數 T 使得 P^T = I（恆等置換）。
• 給定 s 次置換後的序列 B = P^s(A)，求 A = P^{-s}(B) = P^{T - s%T}(B)。
• 先通過重複平方求出循環節 T（或直接模擬直到回到初始）。
• 再對 B 執行 (T - s%T) 次置換得到 A。

代碼實現

#include <cstdio>
#include <cstring>
int a[1010], b[1010], c[1010];
int main() {
    int n, s;
    while (~scanf("%d%d", &n, &s)) {
        for (int i=1;i<=n;i++) scanf("%d",&a[i]), b[i]=a[i], c[i]=a[i];
        int cycle = 0;
        do { // 求循環節
            cycle++;
            for (int i=1;i<=n;i++) b[i] = c[c[i]];
            for (int i=1;i<=n;i++) c[i] = b[i];
        } while (memcmp(a, b, sizeof(a)) != 0); // 直到回到初始
        s %= cycle; s = cycle - s; // 逆操作次數
        while (s--) {
            for (int i=1;i<=n;i++) b[i] = a[a[i]];
            for (int i=1;i<=n;i++) a[i] = b[i];
        }
        for (int i=1;i<=n;i++) printf("%d\n", a[i]);
    }
    return 0;
}

複雜度

• 求循環節：O(T·n)，T 通常很小（≤ n）。
• 逆置換：O(s·n)，s < T。
• 總體 O(n²) 以內，n≤1000 極快。