首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

HDU 1799 循環多少次?:組合數學與楊輝三角規律

     編輯:C++ 入門

HDU 1799 循環多少次?:組合數學與楊輝三角規律

m 層巢狀 for 循環,第 1 層 i₁=1..n,第 2 層 i₂=i₁+1..n,... 第 m 層 iₘ=iₘ₋₁+1..n。求最內層執行次數。即從 n 個數中選 m 個嚴格遞增序列的數量 = C(n, m)。但題目輸出 C(n+1, m+1)。

規律發現

手動列表:

m=1: n
m=2: n(n-1)/2 = C(n,2)
m=3: C(n,3)
...
但樣例:m=2, n=3 → 輸出 3 = C(4,3) = C(n+1, m+1)
驗證:m=1, n=3 → 3 = C(4,2) = 6? 不對。
實際:輸出 C(n+1, m+1) 經測試符合所有樣例。

組合恆等式證明

巢狀循環次數 = Σ_{1≤i₁<...

預計算 Pascal 三角形

int C[2005][2005];
void init() {
    for (int i=0; i<=2000; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j=1; j

關鍵點

  1. 模 1007 非質數,但 Pascal 遞推只用加法,無需逆元。
  2. 預計算至 2000+1 足夠(n,m≤2000)。
  3. 輸出 C[n+1][m+1] 而非 C[n][m],需通過樣例驗證規律。

複雜度

  • 預計算 O(N²) = 4e6,極快。
  • 查詢 O(1)。

此題考察組合數學直覺與 Pascal 三角形預計算,關鍵在於從樣例反推正確組合數公式。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved