CSES 1635 - Coin Combinations I

1.0s 512M

考慮一個由 \(n\) 種硬幣組成的貨幣系統，每種硬幣有一個正整數的面額。你的任務是計算有多少種不同的方式可以用這些硬幣湊出金額 \(x\)。

例如，若硬幣面額為 \(\{2, 3, 5\}\) 且目標金額為 \(9\)，共有 \(8\) 種方式：

\(2+2+5\)
\(2+5+2\)
\(5+2+2\)
\(3+3+3\)
\(2+2+2+3\)
\(2+2+3+2\)
\(2+3+2+2\)
\(3+2+2+2\)

第一行包含兩個整數 \(n\) 和 \(x\)：硬幣種類數與目標金額。

第二行包含 \(n\) 個相異整數 \(c_1, c_2, \ldots, c_n\)：每種硬幣的面額。

輸出一個整數：方法數對 \(10^9 + 7\) 取模後的結果。

3 9
2 3 5

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。

題目頁說明