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關鍵點
複雜度
此題考察組合數學直覺與 Pascal 三角形預計算,關鍵在於從樣例反推正確組合數公式。