陳品叡

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. int mod = 1000000007;
   
5. vector <int> dp;
   
6. vector <int> coin;
   
7. vector <int> visited;
   
8. 
   
9. int aa(int &n, int x)
   
10. {
    
11.     if(visited[x])   return dp[x];
    
12.     for(int i=0; i<n; i++)
    
13.     {
    
14.         if(coin[i]<=x)
    
15.         {
    
16.             dp[x] += aa(n, x-coin[i]);
    
17.             dp[x]%=mod;
    
18.         }
    
19.     }
    
20.     //cout << x << " " << dp[x] << endl;
    
21.     visited[x]++;
    
22.     return dp[x];
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.     int n, x;
    
28.     cin >> n >> x;
    
29.     dp.resize(x);
    
30.     visited.resize(x);
    
31.     coin.resize(n);
    
32.     dp[0]++;
    
33.     for(int i=0; i<n; i++)
    
34.         cin >> coin[i];
    
35.     cout << aa(n, x);
    
36.     return 0;
    
37. }

複製代碼