CSES Problem Set
Coin Combinations II
Consider a money system consisting of coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered 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:
3
#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
inline int power(int a, int b){ int x = 1; while (b) { if (b & 1) x *= a; a *= a; b >>= 1; } return x;}
template <typename Arg1>void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }template <typename Arg1, typename... Args>void __f(const char *names, Arg1 &&arg1, Args &&...args){ const char *comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);}
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]; }
vector<int> dp(x + 1, 0); dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = v[i]; j <= x; j++) { (dp[j] += (dp[j - v[i]]) % N) %= 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.