Advertisement
LEGEND2004

Coin Combinations I

Aug 24th, 2023
934
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.51 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. const int INF = 1e9;
  6. const int mod = 1e9 + 7;
  7. const int N = 1e6 + 5;
  8. int dp[N];
  9.  
  10. signed main()
  11. {
  12.     int n , x;
  13.     cin >> n >> x;
  14.     int a[n + 5];
  15.     for(int i = 0; i < n; i++){
  16.         cin >> a[i];
  17.     }
  18.     dp[0] = 1;
  19.     for(int i = 1; i <= x; i++){
  20.         for(int j = 0; j < n; j++){
  21.             if(i >= a[j])
  22.                 dp[i] += dp[i - a[j]];
  23.             dp[i] %= mod;
  24.         }
  25.     }
  26.     cout << dp[x] << endl;
  27. }
  28.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement