UVALive 3641 列奧納多筆記本：置換平方根與波利亞定理的應用

問題背景

給定一個 26 個大寫字母的排列 B，判斷是否存在排列 A 使得 A² = B（即 A 作用兩次得到 B）。這是群論中尋找置換平方根的問題。

數學原理：置換循環結構

置換可分解為不相交循環。關鍵性質：

• 奇數長度循環：平方後仍為同長度循環，總能找到平方根。
• 偶數長度循環：平方後分解為兩個長度相同的循環。因此，B 中每種偶數長度的循環數量必須為偶數，才能兩兩配對還原為 A 的循環。

判斷算法

1. 對輸入排列進行循環分解，統計各長度循環的個數 len[L]。
2. 檢查所有偶數長度 L：若 len[L] 為奇數，則無解，輸出 "No"。
3. 否則輸出 "Yes"。

C++ 實現

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char str[30]; scanf("%s", str);
        bool vis[26] = {0};
        int len[50] = {0};
        for (int i = 0; i < 26; i++) {
            if (vis[i]) continue;
            int loop = 0, id = i;
            do {
                loop++;
                vis[id] = true;
                id = str[id] - 'A';
            } while (!vis[id]);
            len[loop]++;
        }
        bool ok = true;
        for (int i = 2; i <= 40; i += 2)
            if (len[i] % 2) ok = false;
        puts(ok ? "Yes" : "No");
    }
    return 0;
}

樣例解析

• QWERTYUIOPASDFGHJKLZXCVBNM：含長度為 2 的循環奇數個 → No
• ABCDEFGHIJKLMNOPQRSTUVWXYZ：全為長度 1 循環 → Yes

總結

本題巧妙應用了置換群的循環結構性質，將複雜的代數問題轉化為簡單的循環長度計數與奇偶性判斷，體現了數學思維在算法競賽中的強大威力。