您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 1850 / 1496 組合數學：字典序單詞排名計算（楊輝三角預處理）

編輯：C++ 入門

題目大意

所有「合法單詞」按以下規則排序編號：

單詞長度遞增（先長度 1，再長度 2...）。
同長度按字典序遞增。
合法單詞：由小寫字母組成，字母嚴格遞增（如 abc 合法，aba、acb 不合法）。

給定一個合法單詞，求其編號（從 1 開始）。

核心洞察：組合數對應

長度為 L 的合法單詞，本質上是從 26 個字母中選 L 個並按序排列，數量為 C(26, L)。編號計算可分兩步：

累加所有長度較短的合法單詞數：Σ_{i=1}^{L-1} C(26, i)。
在長度 L 的單詞中，計算給定單詞的字典序排名。

字典序排名計算

對單詞 s[0..L-1] 逐字元處理：

第 0 位：可選字母 'a' ~ s[0]-1。若選 c，剩餘 L-1 位從 c+1 ~ 'z' 中選 → C('z'-c, L-1) 種。
第 i 位：前綴已定為 s[0..i-1]。當前可選 s[i-1]+1 ~ s[i]-1。若選 c，剩餘 L-i-1 位從 c+1 ~ 'z' 選 → C('z'-c, L-i-1)。

累加所有這種「比當前單詞字典序小」的組合數，再 +1 即為排名。

預處理：楊輝三角計算組合數

const int MAXC = 27;
long long C[MAXC][MAXC];
void initComb() {
    for (int i = 0; i < MAXC; ++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];
    }
}

C[n][k] 存 C(n,k)。n ≤ 26 時 C(26,13) ≈ 10⁷，long long 足夠。

完整程式碼（POJ 1496 多測資版 / POJ 1850 單測資版）

#include <bits/stdc++.h>
using namespace std;
const int MAXC = 27;
long long C[MAXC][MAXC];

void initComb() {
    for (int i = 0; i < MAXC; ++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];
    }
}

long long solve(const string& s) {
    int L = s.length();
    // 檢查合法性：嚴格遞增
    for (int i = 1; i < L; ++i)
        if (s[i-1] >= s[i]) return 0;

    long long rank = 1; // 編號從 1 開始
    // 1. 累加較短長度
    for (int i = 1; i < L; ++i) rank += C[26][i];

    // 2. 同長度字典序排名
    for (int i = 0; i < L; ++i) {
        char start = (i == 0) ? 'a' : s[i-1] + 1;
        for (char c = start; c < s[i]; ++c) {
            int remain = L - i - 1;
            int choices = 'z' - c;
            if (choices >= remain) rank += C[choices][remain];
        }
    }
    return rank;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    initComb();
    string s;
    // POJ 1496: 多行輸入，EOF 結束
    // POJ 1850: 單行輸入
    while (cin >> s) {
        cout << solve(s) << '\n';
    }
    return 0;
}