From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 03_dynamic_programming/dice_combinations_1633.cpp | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) create mode 100644 03_dynamic_programming/dice_combinations_1633.cpp (limited to '03_dynamic_programming/dice_combinations_1633.cpp') diff --git a/03_dynamic_programming/dice_combinations_1633.cpp b/03_dynamic_programming/dice_combinations_1633.cpp new file mode 100644 index 0000000..4e76d1d --- /dev/null +++ b/03_dynamic_programming/dice_combinations_1633.cpp @@ -0,0 +1,19 @@ +#include +#include +#include + +// We use a funny memory optimization: we only store the last 7 values. + +int main() { + constexpr unsigned mod = 1e9+7; + int n; + std::cin >> n; + std::array v{0}; + v[0] = 1; + for (int i = 1; i <= n; i++) { + v[i%7] = 0; + for (int j = std::max(0, i-6); j < i; j++) + v[i%7] = (v[i%7]+v[j%7]) % mod; + } + std::cout << v[n%7] << "\n"; +} -- cgit v1.3