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_i_1635.cpp | 25 ++++++++++++++++++++++ 1 file changed, 25 insertions(+) create mode 100644 03_dynamic_programming/coin_combinations_i_1635.cpp (limited to '03_dynamic_programming/coin_combinations_i_1635.cpp') diff --git a/03_dynamic_programming/coin_combinations_i_1635.cpp b/03_dynamic_programming/coin_combinations_i_1635.cpp new file mode 100644 index 0000000..696c1f6 --- /dev/null +++ b/03_dynamic_programming/coin_combinations_i_1635.cpp @@ -0,0 +1,25 @@ +#include +#include + +static constexpr int mod = 1000000007; +static constexpr int X = 1000001; + +int f(const std::vector& c, std::vector& a, int x) { + if (x < 0) return 0; + if (a[x] != -1) return a[x]; + if (x == 0) return a[x] = 1; + + a[x] = 0; + for (auto m : c) + a[x] = (a[x] + f(c, a, x-m)) % mod; + return a[x]; +} + +int main() { + int n, x; + std::cin >> n >> x; + std::vector c(n), a(X, -1); + for (int i = 0; i < n; i++) + std::cin >> c[i]; + std::cout << f(c, a, x) << "\n"; +} -- cgit v1.3