UVA 10910 Marks Distribution：組合數學 (插板法) 與 DP 遞推雙解法

問題

N 門課，總分 T，每門最低 P 分 (P≤T/N)。求分數分配方案數。N,T,P ≤ 70，答案符合 32 位有符號整數。

轉化：放球入盒

每門先給 P 分，剩餘 M = T - N*P 分任意分配到 N 門 (可得 0 分)。即將 M 個相同球放入 N 個不同盒，允許空盒。

解法一：組合數學 (插板法) O(1)

N 個盒需 N-1 個隔板。M 球 + N-1 隔板 = M+N-1 個位置，選 N-1 個放隔板：
C(M+N-1, N-1) = C(T - N*P + N - 1, N - 1)

long long C(long long n, long long k) {
    if (k > n-k) k = n-k;
    long long ans = 1;
    for (int i=1; i<=k; ++i) ans = ans * (n-i+1) / i;
    return ans;
}
// 主程序
M = T - N*P;
ans = C(M+N-1, N-1);

解法二：DP 遞推 O(N·M)

dp[i][j] = 前 i 門課分配 j 分的方案數。
dp[i][j] = sum_{k=0..j} dp[i-1][k]
初始 dp[i][0]=1。優化：dp[i][j] = dp[i][j-1] + dp[i-1][j] (前綴和)。

for (int i=1;i<=N;i++) dp[i][0]=1;
for (int i=1;i<=N;i++)
  for (int j=1;j<=M;j++)
    dp[i][j] = dp[i][j-1] + dp[i-1][j];

複雜度與選擇

• 組合數 O(N) 乘除，最快最簡，推薦。
• DP O(N·M) ≈ 70×70=4900，亦極快，適合理解遞推關係。