給定?V種貨幣（單位：元），每種貨幣使用的次數不限。

不同種類的貨幣，面值可能是相同的。

現在，要你用這?V種貨幣湊出?N?元錢，請問共有多少種不同的湊法。

輸入格式

第一行包含兩個整數?V?和?N。

接下來的若干行，將一共輸入?V?個整數，每個整數表示一種貨幣的面值。

輸出格式

輸出一個整數，表示所求總方案數。

數據范圍

1≤V≤25,
1≤N≤10000
答案保證在long long范圍內。

輸入樣例：

3 10
1 2 5

輸出樣例：

10

?

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;// 定義長整型別名，方便后續使用
typedef long long LL;// 定義常量 N 和 M，分別表示物品數量上限和背包容量上限
const int N = 30, M = 10010;// n 表示物品數量，m 表示背包容量
int n, m;
// v 數組用于存儲每個物品的體積
int v[N];
// f 數組用于存儲狀態，f[i][j] 表示前 i 個物品裝滿容量為 j 的背包的方案數
LL f[N][M];int main()
{// 從標準輸入讀取物品數量 n 和背包容量 mscanf("%d%d", &n, &m);// 循環讀取每個物品的體積for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);// 初始化狀態，當沒有物品且背包容量為 0 時，方案數為 1f[0][0] = 1;// 動態規劃過程，枚舉每個物品for (int i = 1; i <= n; i ++ )// 枚舉背包的每個容量for (int j = 0; j <= m; j ++ ){// 不選擇第 i 個物品的方案數f[i][j] = f[i - 1][j];// 如果當前背包容量 j 大于等于第 i 個物品的體積 v[i]if (j >= v[i]) // 選擇第 i 個物品的方案數，累加到 f[i][j] 中f[i][j] += f[i][j - v[i]];}// 輸出前 n 個物品裝滿容量為 m 的背包的方案數printf("%lld\n", f[n][m]);return 0;
}