HDU 1261 字串數：多重集排列計數與大整數運算實現

問題描述

給定 n 種字母及其個數 a₁, a₂, ..., aₙ，求能組成的不同字符串總數。本質是多重集排列計數：

Ans = (Σaᵢ)! / (a₁! × a₂! × ... × aₙ!)

挑戰：超大整數運算

最大情況：26 種字母各 12 個，總長 312。312! 約 10⁶⁵⁰，遠超 64 位整數範圍。需實現高精度乘法與除法。

算法設計

1. 高精度乘法：模擬手工乘法

用數組 ans[] 存儲大整數（低位在前），逐位乘以 2..N，處理進位。

2. 高精度除法：模擬手工長除法

對每個 aᵢ! 進行除法。預計算 1..12 的階乘值 f[]。從高位向低位試商，處理餘數。

3. 優化：分子分母約分

直接計算 (Σaᵢ)! / Π(aᵢ!) 避免中間結果過大。代碼採用「先乘後除」策略，利用整除性質保證無餘數。

核心代碼

#include 
#define SIZE 30
typedef long long ll;
int d[SIZE], ans[1000], f[15];

void multiply(int c) { // 計算 c!
    ans[0] = ans[1] = 1;
    for (int i = 2; i <= c; i++) {
        int r = 0;
        for (int j = 1; j <= ans[0]; j++) {
            ans[j] *= i; ans[j] += r;
            r = ans[j] / 10; ans[j] %= 10;
        }
        while (r) { ans[++ans[0]] = r % 10; r /= 10; }
    }
}

void divide(int n) { // 除以 d[0]! ... d[n-1]!
    for (int i = 0; i < n; i++) {
        if (d[i] == 1) continue;
        ll r = 0;
        for (int j = ans[0]; j > 0; j--) {
            r = r * 10 + ans[j];
            ans[j] = r / f[d[i]];
            r %= f[d[i]];
        }
        while (ans[ans[0]] == 0) ans[0]--;
    }
}

int main() {
    f[0] = f[1] = 1;
    for (int i = 2; i < 15; i++) f[i] = f[i-1] * i;
    int n;
    while (scanf("%d", &n) && n) {
        int sum = 0; memset(ans, 0, sizeof(ans));
        for (int i = 0; i < n; i++) { scanf("%d", &d[i]); sum += d[i]; }
        multiply(sum); divide(n);
        for (int i = ans[0]; i > 0; i--) printf("%d", ans[i]);
        puts("");
    }
    return 0;
}

最大測試輸出

26 個 12 的輸出為 650 位數字（文中已給出完整結果），驗證了算法正確性。

總結

本題結合組合數學公式與高精度四則運算，是大整數處理的優秀練習。「先乘總階乘，再逐個除以分母階乘」的策略簡潔有效，利用了結果必為整數的性質避免了複雜的約分邏輯。