b593. Code

---

解法一、數學

🔹 組合

題目可以解讀為：

給一字串 s
求滿足 s[i] < s[j]，其中 i < j
且 < s 的字串數量

用組合計算所求

數學解釋

先看個題目：

1~9 數字中隨機挑三個不同的數字組成一個三位數
求符合 百位數 < 十位數 < 個位數 的三位數有多少

Ans：

這裡不需要考慮被選出數字的順序
因為不管順序是什麼最後都會由小到大排列
因此只考慮組合數：$C_{3}^{9}$

— — —

接下來看 a~z 取 n 個字母的版本
可以知道答案為 $C_{n}^{26}$

s = "ceh"

以 s = "ceh" 舉例

"ceh" 對應的數字
= 小於 "ceh" 且符合題目條件的字串數量
= 長度 < 3 + 長度 = 3 < "ceh" 且符合題目條件的字串數量

分成兩個部分計算

🔸 Part I：處理長度 < 3

所有長度 < 3 的字串一定 < "ceh"
直接計算所有狀況的總和

考慮長度 = 1

個數總和為 $C_{1}^{26}$

考慮長度 = 2

個數總和為 $C_{2}^{26}$

🔸 Part II：處理長度 = 3

長度 = 3 需要分開考慮
由 s 的最高位開始，由 "a" ~ s[0]
接著考慮 s 的第二高位，由 "s[0]" ~ s[1]
…以此類推

考慮最高位

對於 長度 = 3 的字串
如果最高位 < "c"，則這字串一定 < "ceh"
(例 "akz"、"bpy")

• 對於最高位 = "a"

固定最高位 "b"，而後面的數不能 <= "b"
因此 26-1個字母(少 "a" 1個) 取 2個
個數總和為 $C_{2}^{25}$

• 對於最高位 = "b"

固定最高位 "b"，而後面的數不能 <= "b"
因此 26-2個字母(少 "a", "b" 2個) 取 2個
個數總和為 $C_{2}^{24}$

考慮第二高位

如果最高位 = "c"
第二高位 < "e"，則這字串一定 < "ceh"
(例 "cbk"、"cdj")

(注意，考慮 第二高位 時一樣不能小於 最高位，所以從 "d" 開始)

• 對於第二高位 = "d"

固定最高位 "c"，與第二高位 "d"
而後面的數不能 <= "d"
因此 26-4個字母 取 1個
個數總和為 $C_{1}^{22}$

考慮第三高位

如果最高位 = "c"
第二高位 = "e" 第三高位 < "h"，則這字串一定 < "ceh"
(例 "cef"、"ceg")

(注意，考慮 第三高位 時一樣不能小於 第二高位，所以從 "f" 開始)

• 對於第三高位 = "f"

固定最高位 "c"，與第二高位 "e"，與第三高位 "f"
個數為 $1$

• 對於第三高位 = "g"

固定最高位 "c"，與第二高位 "e"，與第三高位 "g"
個數為 $1$

— — —

以上求出了 < "ceh" 的字串個數
所求需要再 +1 ("ceh" 本身)

所以 "ceh" 對應的數字為
$C_{1}^{26} + C_{2}^{26} + C_{2}^{25} + C_{2}^{24} + C_{1}^{22} + 1 + 1 + 1 = 952$

這裡可以事先計算 $C_{k}^{n}$
避免之後要用都要重新計算

公式：
$C_{k}^{n} = C_{k-1}^{n-1} + C_{k}^{n-1}$

✅ 完整代碼

評分結果(參考) ： AC (1ms, 316KB)

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    string s;
    while(true) {
        cin >> s;
        if(s == "0") break;
        
        int ans = 1;
        for(int k=1; k<s.size(); k++) {
            ans += C[26][k];
        }

        int curr, prev = 'a'-1;
        for(int i=0; i<s.size(); i++) {
            curr = s[i];
            if(curr <= prev) {
                ans = 0;
                break;
            }

            for(int c=(prev+1); c<curr; c++) {
                int n = 26-(c-'a')-1;
                int k = s.size()-i-1;
                ans += C[n][k];
            }
            prev = curr;
        }

        cout << ans << "\n";
    }
    
    return 0;
}