HDOJ 4259 Double Dealing - 洗牌循環節 LCM 求回到原序列次數

問題描述

有 n 張不同的牌，發給 k 個玩家：第 1 張給玩家 1，第 2 張給玩家 2，... 第 k 張給玩家 k，第 k+1 張又給玩家 1，以此類推。發完後，按玩家 1..k 的順序疊回，每位玩家手中牌順序反轉（最後發到的在最上）。問重複多少次此過程後牌序回到初始順序。

置換建模

一次操作確定一個置換 next[i]：位置 i 的牌移動到位置 next[i]。模擬一次發牌疊回即可構造 next 數組。然後將置換分解為若干不相交循環，答案為所有循環長度的最小公倍數 (LCM)。

構造置換

1. 計算每位玩家得到的牌數 cnt[p]：前 n%k 位玩家得 ⌈n/k⌉ 張，其餘得 ⌊n/k⌋ 張。
2. 計算玩家 p 的牌在疊回後的起始位置 start[p]（前綴和）。
3. 對於原位置 i (1-indexed)，它屬於玩家 p = (i-1)%k + 1，在該玩家手中是第 t = (i-1)/k + 1 張發到的牌。疊回時該玩家牌順序反轉，所以其在疊回堆中的位置為 start[p] + cnt[p] - t。即 next[i] = start[p] + cnt[p] - t。

複雜度

O(n) 構造置換，O(n) 分解循環，n ≤ 800 瞬間完成。答案保證在 64 位有符號整數範圍內。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a,b) * b; }

int n, k;
int nxt[805], cnt[805], start[805];
bool vis[805];

int main() {
    while (scanf("%d%d", &n, &k) == 2) {
        if (n==0 && k==0) break;
        if (n <= k) { puts("1"); continue; }
        // 計算每位玩家牌數
        for (int i = 1; i <= k; ++i) cnt[i] = n/k + (i <= n%k);
        start[1] = 1;
        for (int i = 2; i <= k; ++i) start[i] = start[i-1] + cnt[i-1];
        // 構造置換
        for (int i = 1; i <= n; ++i) {
            int p = (i-1)%k + 1;
            int t = (i-1)/k + 1;
            nxt[i] = start[p] + cnt[p] - t;
        }
        // 分解循環求 LCM
        memset(vis, 0, sizeof(vis));
        LL ans = 1;
        for (int i = 1; i <= n; ++i) if (!vis[i]) {
            int len = 0, u = i;
            while (!vis[u]) { vis[u] = true; u = nxt[u]; ++len; }
            ans = lcm(ans, len);
        }
        printf("%lld\n", ans);
    }
    return 0;
}