HDU 1398 Square Coins：母函數求硬幣組合數

銀幣面值為完全平方數（1, 4, 9, ..., 289），每種無限供給。給定金額 n (<300)，求付款組合數（順序不分）。多組測試，0 結束。

母函數建模

第 k 種硬幣 (面值 k²) 的母函數為 1 + x^{k²} + x^{2k²} + ...。所有硬幣母函數乘積中，x^n 的係數即為答案。動態規劃實現多項式乘法：

• dp[i] 表示當前處理到的硬幣組合下，湊成金額 i 的方案數。
• 初始 dp[0..n] = 1（只有 1 元硬幣時只有 1 種方案）。
• 對每種硬幣面值 v = k*k，對 j=0..n、k=0; j+k<=n; k+=v 更新 new_dp[j+k] += dp[j]。

參考代碼

#include 
using namespace std;
int dp[302], tmp[302];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n && n) {
        fill(dp, dp + n + 1, 1);
        fill(tmp, tmp + n + 1, 0);
        for (int k = 2; k * k <= n; k++) {
            int v = k * k;
            for (int j = 0; j <= n; j++) {
                for (int s = 0; j + s <= n; s += v) {
                    tmp[j + s] += dp[j];
                }
            }
            copy(tmp, tmp + n + 1, dp);
            fill(tmp, tmp + n + 1, 0);
        }
        cout << dp[n] << "\n";
    }
    return 0;
}

複雜度

硬幣種類 ≤ 17，金額 ≤ 300，三層迴圈實際操作數極小，瞬間通過。