Codeforces 459C Pashmak and Buses：K 進制構造數列避免學生全天同車

問題重述

n 名學生，k 輛車（容量無限），d 天。每天安排每學生乘坐某輛車。要求：不存在兩名學生在 d 天內每天都乘坐同一輛車（即任意兩學生的 d 天乘車序列至少有一天不同）。輸出 d 行每行 n 個數表示每天安排，或 -1 表示不可能。

核心洞察：K 進制編碼

將每名學生分配一個唯一的 d 位 K 進制數（共 K^d 種組合）。若 K^d < n，鴿巢原理必有兩學生序列完全相同 → 輸出 -1。否則，第 i 名學生（0-indexed）的第 j 天（0-indexed）乘車號為：

bus = (i / K^j) % K + 1

即將學生編號 i 寫成 d 位 K 進制，第 j 位（從低位到高位）對應第 j 天的車號（+1 避免 0）。

正確性證明

任意兩學生編號不同 → 其 K 進制表示至少一位不同 → 對應那天乘車不同。完美滿足條件。

實現細節

• 用 64 位整數檢查 K^d >= n，溢出時提前判斷為 true
• 預計算所有學生的 d 天車號存入二維陣列 ans[student][day]
• 輸出時按天為外層循環，學生為內層循環

代碼實現

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
int ans[1005][1005];
int main() {
    int n, d, k;
    while (~scanf("%d%d%d", &n, &k, &d)) {
        bool ok = false;
        LL prod = 1;
        for (int i = 1; i <= d; ++i) {
            prod *= k;
            if (prod >= n) { ok = true; break; }
        }
        if (!ok) { puts("-1"); continue; }
        for (int i = 0; i < n; ++i) {
            LL tmp = i;
            for (int j = 0; j < d; ++j) {
                ans[i][j] = tmp % k + 1;
                tmp /= k;
            }
        }
        for (int day = 0; day < d; ++day) {
            for (int stu = 0; stu < n; ++stu) {
                printf("%d%c", ans[stu][day], stu == n-1 ? '\n' : ' ');
            }
        }
    }
    return 0;
}

複雜度與擴展

時間 O(n d)，空間 O(n d)。n, d ≤ 1000，k ≤ 1e9，完全滿足限制。此題展示了「進制表示」在組合構造中的巧妙應用。