UVA 10458 Cricket Ranking：容斥原理計算有界組合數

問題描述

給定 k 個區間 [l_i, r_i]，從每個區間選一個整數，求和為 n 的方案數。結果可能極大，需高精度輸出。

數學轉化

令 x_i ∈ [l_i, r_i]，設 y_i = x_i - l_i ≥ 0，則 y_i ≤ f_i = r_i - l_i。原問題等價於：

y_1 + ... + y_k = n - sum(l_i) = S，其中 0 ≤ y_i ≤ f_i。

容斥原理求解

無上界時，非負整數解數為 C(S + k - 1, k - 1)（隔板法）。引入上界 y_i ≤ f_i，用容斥：

• 枚舉子集 mask ⊆ {1..k}，表示強制 y_i ≥ f_i+1 的變量集合。
• 令 S' = S - Σ_{i∈mask} (f_i + 1)。若 S' < 0 則該子集貢獻 0。
• 方案數 C(S' + k - 1, k - 1)。
• 符號：|mask| 為奇數減，偶數加（含空集）。

答案 = Σ_{mask} (-1)^{|mask|} C(S' + k - 1, k - 1)。

高精度組合數計算

k ≤ 10，n, f_i 較大，組合數超出 64 位。代碼實現了十進制高精度結構體 bign，支援加減乘除（除以 int）、比較、輸出。組合數通過公式 C(n,m) = Π_{i=0}^{m-1} (n-i)/(i+1) 逐步乘除計算，中間保持整數。

複雜度

• 枚舉 2^k ≤ 1024 子集。
• 每個子集計算組合數 O(k) 乘除高精度數。
• 總體極快。

核心代碼片段

// 高精度結構體 bign 略（支援 +, -, *, /int, 輸出）
int k; long long n, f[10];
int bitcount(int x){ return x?bitcount(x>>1)+(x&1):0; }
bign C(long long n, long long m){
    bign ans=1;
    for(long long i=0;i