CSES Problem Set
Coin Combinations I
Consider a money system consisting of coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum using the available coins.
For example, if the coins are and the desired sum is , there are ways:
The first input line has two integers and : the number of coins and the desired sum of money.
The second line has distinct integers : the value of each coin.
Output
Print one integer: the number of ways modulo .
Constraints
Input:
Output:
For example, if the coins are and the desired sum is , there are ways:
The first input line has two integers and : the number of coins and the desired sum of money.
The second line has distinct integers : the value of each coin.
Output
Print one integer: the number of ways modulo .
Constraints
Input:
3 9
2 3 5
Output:
8
Solution To the Above problem
#include <bits/stdc++.h>
using namespace std;
#define int long long int#define F first#define S second#define pb push_back#define si set <int>#define vi vector <int>#define pii pair <int, int>#define vpi vector <pii>#define vpp vector <pair<int, pii>>#define mii map <int, int>#define mpi map <pii, int>#define spi set <pii>#define endl "\n"#define sz(x) ((int) x.size())#define all(p) p.begin(), p.end()#define double long double#define que_max priority_queue <int>#define que_min priority_queue <int, vi, greater<int>>#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)#define print(a) for(auto x : a) cout << x << " "; cout << endl#define print1(a) for(auto x : a) cout << x.F << " " << x.S << endl#define print2(a,x,y) for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
const int N = 1e9+7;
void solve() {
int n,x;cin>>n>>x;
vi v(n);for (int i = 0; i < n; i++){ cin>>v[i];}vi dp(x+1,0);for(int i=0; i<=x; i++){ for(int j=0; j<n; j++){ if(v[j]==i)dp[i]++; if(i-v[j]>=0) dp[i]+=(dp[i-v[j]])%N; dp[i]%=N; }}
cout<<dp[x];
}
int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
clock_t z = clock();
int t = 1;// cin >> t; while (t--) solve();
return 0;}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.