# Coin Combinations I - C++

Sep 27th, 2020
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. typedef long long ll;typedef long double llf;typedef double fl;typedef string str;typedef pair<double, double> dd;
5. typedef vector<int> vi;typedef vector<vector<int>> vvi;typedef vector<fl> vf;typedef vector<ll> vl;
6. typedef vector<llf> vlf;typedef vector<char> vc;typedef vector<str> vs;typedef pair<int,int> ii;
7. # define f(i,a,b,c) for(ll i=a;i<b;i+=c)
8. # define fd(i,a,b,c) for(ll i=a;i>=b;i-=c)
9. # define w(x) while(x--)
10. # define ctoi(a) (a-'0')
11. # define pb push_back
12. # define eb emplace_back
13. # define lb lower_bound
14. # define ub upper_bound
15. # define be(x) x.begin(), x.end()
16. # define rbe(x) x.rbegin(), x.rend()
17. # define _(x) ios::sync_with_stdio(0);cin.tie(0);cout.precision(x);cout.setf(ios::fixed);
18.
19. const int MOD = 1e9+7, MAX = 100000010;
20. ll n, m, coins[100], memo[MAX], confirm[MAX];
21. ll dp(ll x){
22.     if(x<0)return 0;
23.     if(x==0)return 1;
24.     if(confirm[x])return memo[x]%MOD;
25.     confirm[x]=1;
26.     ll sum_coins=0;
27.     f(i,0,n,1)sum_coins+=dp(x-coins[i]);
28.     return memo[x]=sum_coins;
29. }
30. int main(){_(0)
31.     cin>>n>>m;
32.     f(i,0,n,1)cin>>coins[i];
33.     cout<<dp(m)%MOD<<'\n';
34. return 0;}