UVALive 6814 Lexicography：字典序第 K 個字母異位詞

題目大意

給定一個單詞（大寫字母，長度 ≤ 16）和排名 K（≤ 2^45，需 64 位整數），求其所有字母異位詞（全排列去重）按字典序排列時第 K 個。輸入以 "# 0" 結束。

核心思路：逐位構造 + 組合計數

預計算階乘 fact[i] (i≤16)。統計各字母出現次數 cnt[26]。從最高位開始，嘗試填入 'A'~'Z'：

• 若該字母可用（cnt>0），暫用一次，計算剩餘字母的全排列數：ways = fact[rem] / Π fact[cnt[i]]。
• 若 K > ways，說明目標不在以此字母開頭的區塊，K -= ways，嘗試下一字母。
• 否則確定該字母為當前位，永久遞減其 cnt，進入下一位。

關鍵細節

• 使用 unsigned long long 或 __int128 存儲 K 和 ways，防止溢出（2^45 約 3.5e13，16! ≈ 2e13，64 位足夠）。
• 除法需精確：先計算分子階乘，再依次除以各字母階乘，保證整除。
• 字母順序 'A'~'Z' 即字典序。

完整代碼

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef unsigned long long ULL;

ULL fact[20];
int cnt[26];
char str[20];
ULL K;

ULL countPerm(int rem) {
    ULL res = fact[rem];
    for (int i = 0; i < 26; i++)
        res /= fact[cnt[i]];
    return res;
}

int main() {
    fact[0] = 1;
    for (int i = 1; i <= 16; i++) fact[i] = fact[i-1] * i;
    while (scanf("%s %llu", str, &K) == 2) {
        if (str[0] == '#' && K == 0) break;
        memset(cnt, 0, sizeof(cnt));
        int len = strlen(str);
        for (int i = 0; i < len; i++) cnt[str[i]-'A']++;
        for (int pos = 0; pos < len; pos++) {
            for (int c = 0; c < 26; c++) {
                if (cnt[c] == 0) continue;
                cnt[c]--;
                ULL ways = countPerm(len - pos - 1);
                if (K > ways) {
                    K -= ways;
                    cnt[c]++; // 還原，試下一個
                } else {
                    putchar('A' + c);
                    break; // 確定該字母，進入下一位
                }
            }
        }
        putchar('\n');
    }
    return 0;
}

複雜度分析

• 預處理 O(16)。
• 每測試案例：O(長度 * 26) ≈ O(400)，極快。

總結

本題是「字典序第 K 個排列」的經典變體：含重複元素。核心是利用多重集排列公式快速計算以某前綴開頭的排列數，逐位貪心確定字符。注意大整數運算用 64 位無符號整數。