POJ 1959 Darts 允許重複組合的三鏢得分計數

問題

標準飛鏢盤分值：1~20 的單倍、雙倍、三倍，外牛眼 25，內牛眼 50。每種分值有限次數 (單倍 1 次、雙倍 1 次、三倍 1 次、25 一次、50 一次)。三支鏢得分和為 n，求不同組合數 (順序不計)。多測試用例。

預處理分值頻次

構建 `freq[score]`：

• 1~20: freq[i]=1, freq[2i]=1, freq[3i]=1
• freq[25]=1, freq[50]=1
• freq[0]=1 (代表不投/投偏)

三重循環枚舉不降序三元組

int solve(int n) {
    int ans = 0;
    for (int x = 0; x <= min(n,60); ++x)
        for (int y = x; y <= min(n,60); ++y)
            for (int z = y; z <= min(n,60); ++z)
                if (x+y+z == n) {
                    if (x==y && y==z) ans += C(freq[x]+2,3);
                    else if (x==y || y==z) {
                        int m = (x==y)? freq[x] : freq[y];
                        int c = (x==y)? freq[z] : freq[x];
                        ans += C(m+1,2) * c;
                    } else ans += freq[x] * freq[y] * freq[z];
                }
    return ans;
}

組合數計算

C(n,k) 直接用公式：C(m+2,3)=(m+2)(m+1)m/6, C(m+1,2)=(m+1)m/2。

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
int freq[61];

int main() {
    memset(freq, 0, sizeof(freq));
    freq[0] = 1;
    for (int i=1; i<=20; ++i) { freq[i]++; freq[2*i]++; freq[3*i]++; }
    freq[25]++; freq[50]++;
    int T; cin >> T;
    for (int tc=1; tc<=T; ++tc) {
        int n; cin >> n;
        cout << "Scenario #" << tc << ":\n" << solve(n) << "\n\n";
    }
    return 0;
}