本帖最後由 陳品叡 於 2024-8-11 10:52 編輯
- #include <bits/stdc++.h>
- using namespace std;
- int mod = 1000000007;
- vector <int> dp;
- vector <int> coin;
- vector <int> visited;
- int aa(int &n, int x)
- {
- if(visited[x]) return dp[x];
- for(int i=0; i<n; i++)
- {
- if(coin[i]<=x)
- {
- dp[x] += aa(n, x-coin[i]);
- dp[x]%=mod;
- }
- }
- //cout << x << " " << dp[x] << endl;
- visited[x]++;
- return dp[x];
- }
- int main()
- {
- int n, x;
- cin >> n >> x;
- dp.resize(x);
- visited.resize(x);
- coin.resize(n);
- dp[0]++;
- for(int i=0; i<n; i++)
- cin >> coin[i];
- cout << aa(n, x);
- return 0;
- }
複製代碼 |