HDU 1799 循環多少次？：組合數學與楊輝三角的經典應用

問題描述

m 層嵌套循環，第 1 層變量從 1 到 n，第 i 層從上一層變量+1 到 n。求最內層 OP 執行次數。m, n ≤ 2000，結果模 1007。

數學建模：組合數

循環變量滿足：1 ≤ i₁ < i₂ < ... < iₘ ≤ n。這正是從 n 個元素中選 m 個的組合數 C(n, m)！

驗證樣例：n=3, m=2 → C(3,2)=3 ✓；n=3, m=1 → C(3,1)=3 ✓

楊輝三角預計算

C(n, m) = C(n-1, m) + C(n-1, m-1)。預計算 2000×2000 的 Pascal 三角，模 1007。

完整 AC 代碼

#include <cstdio>
const int MAXN = 2000;
const int MOD = 1007;
int C[MAXN + 1][MAXN + 1];

int main() {
    // 楊輝三角預計算
    for (int i = 0; i <= MAXN; ++i) {
        C[i][0] = C[i][i] = 1 % MOD;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
    }
    
    int T; scanf("%d", &T);
    while (T--) {
        int m, n; scanf("%d%d", &m, &n);
        printf("%d\n", C[n][m]);
    }
    return 0;
}

關鍵坑點

1. 數組大小：m,n ≤ 2000，需開 [2001][2001]，靜態分配約 16MB，安全
2. 模運算時機：每步取模防止溢出，1007 很小 int 足夠
3. 輸入順序：題目給 m n，但組合數是 C(n, m)，注意參數位置
4. 遞歸棧溢出：遞歸實現組合數會 RE，必須用迭代 DP

數學延伸

更通用的：k 層循環，第 i 層從 a_i 到 b_i，可用生成函數或 DP 求解。本題等差約束使其退化為簡單組合數。

複雜度

• 預計算：O(MAXN²) = 4e6 操作，極快
• 查詢：O(1)
• 空間：O(MAXN²) ≈ 16MB