POJ 1496 Word Index——組合數計數求字典序排名

問題描述

合法單詞：長度 1~5，由小寫字母組成，字母嚴格遞增（如 `abc`, `gwz` 合法；`aab`, `cat` 非法）。所有合法單詞按字典序排列編號從 1 開始。輸入一單詞，若非法輸出 0，否則輸出其編號。

核心觀察

• 嚴格遞增 ⇒ 從 26 字母中選 k 個，只有一種排列（升序）。
• 長度 k 的合法單詞數 = C(26, k)。
• 總單詞數 = Σ C(26,k) (k=1..5) = 83681。

排名計算公式

對單詞 `s[0..len-1]`（0-based）：

1. 先加所有長度 < len 的單詞數：`sum = Σ C(26, i) (i=1..len-1)`。
2. 逐位處理：第 i 位（0-based），可選字母從 `prev+1` 到 `s[i]-1`（`prev` 為上一位字母，i=0 時 `prev='a'-1`）。對每個候選字母 `ch`，剩餘 `len-i-1` 位從 `ch+1..'z'` 中選，數目 = C(`'z'-ch`, `len-i-1`)。累加到 `sum`。
3. 最終排名 = `sum + 1`（加上單詞自身）。

例：`ceh` (len=3)

• 短單詞：C(26,1)+C(26,2) = 26+325 = 351
• 第 0 位：候選 `a,b` → C(25,2)+C(24,2) = 300+276 = 576
• 第 1 位：上一位 `c`，候選 `d` → C(22,1) = 22
• 第 2 位：上一位 `e`，候選 `f,g` → C(20,0)+C(19,0) = 1+1 = 2
• 總和 = 351+576+22+2 = 951，排名 = 952

代碼實現

#include 
using namespace std;
int C[27][27];

void initComb() {
    for (int i = 0; i <= 26; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j) C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
}

int main() {
    initComb();
    string s;
    while (cin >> s) {
        int len = s.size();
        bool valid = true;
        for (int i = 1; i < len; ++i)
            if (s[i] <= s[i-1]) { valid = false; break; }
        if (!valid) { cout << 0 << '\n'; continue; }

        int rank = 0;
        for (int i = 1; i < len; ++i) rank += C[26][i];
        char prev = 'a' - 1;
        for (int i = 0; i < len; ++i) {
            for (char ch = prev + 1; ch < s[i]; ++ch)
                rank += C['z' - ch][len - 1 - i];
            prev = s[i];
        }
        cout << rank + 1 << '\n';
    }
    return 0;
}

關鍵點

• 預計算組合數 C[n][k] (n≤26)，O(1) 查詢。
• 合法性檢查：嚴格遞增。
• 字母轉數字：`'z' - ch` 直接得剩餘可選字母數。
• 長度 5 時 `'z'-ch` 可能為 0，C[0][0]=1 正確處理。

複雜度

• 預處理：O(26²) 忽略。
• 每查詢：O(len) ≤ 5，極快。

總結

組合數計數經典應用。嚴格遞增單詞 ↔ 組合選擇，排名計算 = 短單詞數 + 同長度字典序前單詞數。掌握「按位累加組合數」模板，可解決所有「字典序排名/第 k 個組合」類問題。