From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- .../coin_combinations_ii_1636.cpp | 28 ++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 03_dynamic_programming/coin_combinations_ii_1636.cpp (limited to '03_dynamic_programming/coin_combinations_ii_1636.cpp') diff --git a/03_dynamic_programming/coin_combinations_ii_1636.cpp b/03_dynamic_programming/coin_combinations_ii_1636.cpp new file mode 100644 index 0000000..75642da --- /dev/null +++ b/03_dynamic_programming/coin_combinations_ii_1636.cpp @@ -0,0 +1,28 @@ +#include +#include +#include + +static constexpr int mod = 1000000007; +static constexpr int X = 1000001; + +int main() { + int n, x; + std::cin >> n >> x; + std::vector c(n); + for (int i = 0; i < n; i++) + std::cin >> c[i]; + + std::vector> a(n, std::vector(X, 0)); + for (int i = 0; i < (int)c.size(); i++) a[i][0] = 1; + for (int j = c.back(); j <= x; j += c.back()) a[c.size()-1][j] = 1; + for (int i = c.size()-2; i >= 0; i--) { + for (int j = 1; j <= x; j++) { + a[i][j] = a[i+1][j]; + if (j >= c[i]) { + a[i][j] += a[i][j-c[i]]; + a[i][j] %= mod; + } + } + } + std::cout << a[0][x] << "\n"; +} -- cgit v1.3