HDU 1799 循環多少次？ - 組合數學公式 C(n, m) 模 1007

題目大意

m 層巢狀迴圈，第 i 層變量從 i (或上層變量+1) 開始到 n 結束。求內層語句執行總次數。輸出模 1007 結果。T ≤ 10000, m,n ≤ 2000。

數學建模：組合數

等價於從 n 個數中選 m 個 嚴格遞增 的序列，即組合數 C(n, m)。
樣例：m=2, n=3 → C(3,2)=3 (對應 (1,2), (1,3), (2,3))。

遞推公式：帕斯卡三角形

C(n, m) = C(n-1, m) + C(n-1, m-1)，邊界 C(n, 0)=1, C(n, 1)=n。
預計算 c[2000][2000] 取模 1007，查詢 O(1)。

完整代碼

#include 
int c[2020][2020];

void init() {
    for (int i = 1; i < 2020; ++i) {
        c[i][1] = i % 1007;
        c[i][0] = 1;
    }
    for (int i = 2; i < 2020; ++i)
        for (int j = 1; j < 2020; ++j)
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % 1007;
}

int main() {
    init();
    int T; scanf("%d", &T);
    while (T--) {
        int m, n; scanf("%d%d", &m, &n);
        printf("%d\n", c[n][m]); // 注意參數順序：c[n][m] = C(n, m)
    }
    return 0;
}

關鍵細節

• 參數順序：題目給 m n，組合數為 C(n, m)，代碼 c[n][m]。
• 模 1007：非質數，但加法遞推無需逆元，直接取模正確。
• 預計算上限 2020：覆蓋 n,m ≤ 2000。
• 多測資：預計算一次，查詢 O(1)，T=10000 瞬時完成。

複雜度

• 預計算：O(2000²) = 4e6，極快。
• 查詢：O(1)。
• 空間：2020² × 4B ≈ 16MB。