POJ 1496 / 1850 組合計數：字典序單詞編碼問題

問題描述

給定一個僅由小寫字母組成、字母按字典序嚴格遞增的單詞（如 "ab", "bdf"），按照長度優先、同長度按字典序的規則對所有合法單詞編碼（a=1, b=2, ..., z=26, ab=27, ...）。輸入一個單詞，若其字母不嚴格遞增則輸出 0，否則輸出其編碼。單詞長度 ≤ 10。

核心觀察

合法單詞等價於從 26 個字母中選取 k 個（1 ≤ k ≤ 10）並按升序排列，因此長度為 k 的合法單詞數為 C(26, k)。編碼順序：

1. 先按長度遞增：所有長度 1 的單詞，再長度 2，…
2. 同長度內按字典序：即組合的字典序。

目標單詞的編碼 = 所有比它短的合法單詞總數 + 同長度中比它小的合法單詞數 + 1。

算法步驟

1. 合法性檢查：若單詞長度 > 1 且存在 s[i] ≥ s[i+1]，輸出 0。
2. 預計算組合數：用帕斯卡三角形計算 C[n][k] (0 ≤ n,k ≤ 26)。
3. 累加較短單詞數：ans = Σ_{i=1}^{len-1} C(26, i)。
4. 同長度中較小單詞數：對單詞每個位置 i，考慮比 s[i] 大但比後續字母小的可選字母，累加對應組合數。

關鍵代碼片段

// 組合數預計算
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-1] + C[i-1][j];
}

// 同長度排名計算
int len = strlen(s);
for (int i = 0; i < len; i++) {
    char start = (i == 0) ? 'a' : s[i-1] + 1;
    for (char c = start; c < s[i]; c++) {
        int remaining = len - i - 1;
        int available = 'z' - c;
        if (available >= remaining) ans += C[available][remaining];
    }
}

完整代碼（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

long long C[27][27];

void init_comb() {
    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-1] + C[i-1][j];
    }
}

bool valid(const char *s) {
    int len = strlen(s);
    for (int i = 0; i < len-1; i++)
        if (s[i] >= s[i+1]) return false;
    return true;
}

long long solve(const char *s) {
    int len = strlen(s);
    long long ans = 0;
    // 較短長度
    for (int i = 1; i < len; i++) ans += C[26][i];
    // 同長度字典序排名
    for (int i = 0; i < len; i++) {
        char start = (i == 0) ? 'a' : s[i-1] + 1;
        for (char c = start; c < s[i]; c++) {
            int rem = len - i - 1;
            int avail = 'z' - c;
            if (avail >= rem) ans += C[avail][rem];
        }
    }
    return ans + 1;  // 編碼從 1 開始
}

int main() {
    init_comb();
    char s[15];
    while (scanf("%s", s) == 1) {
        if (!valid(s)) printf("0\n");
        else printf("%lld\n", solve(s));
    }
    return 0;
}

複雜度分析

• 預計算：O(26²) ≈ 常數。
• 每查詢：O(L × 26) ≤ 260 操作，極快。
• 空間：O(26²)。

測試樣例

輸入:
bf
輸出:
55
解析: 長度1共26個; 長度2中以a開頭的有25個(ab..az), 以b開頭且第二字母