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/counting_towers_2413.cpp | 38 +++++++++++++++++++++++++ 1 file changed, 38 insertions(+) create mode 100644 03_dynamic_programming/counting_towers_2413.cpp (limited to '03_dynamic_programming/counting_towers_2413.cpp') diff --git a/03_dynamic_programming/counting_towers_2413.cpp b/03_dynamic_programming/counting_towers_2413.cpp new file mode 100644 index 0000000..902956b --- /dev/null +++ b/03_dynamic_programming/counting_towers_2413.cpp @@ -0,0 +1,38 @@ +#include +#include + +// Recurrence relation: +// f(n) = sum over i from 0 to n-1 of f(i) * p(n-i) +// where p(n) is the number of indivisible towers of height n, +// which is easily seen to be 3^(n-1)+1. +// Then we can expand: +// f(n) = sum_{i=0}^{n-1} f(i)(3^{n-i-1}+1) = g(n) + h(n) +// where we define g(n) = sum f(i)3^{n-i-1} and h(n) = sum f(i). +// Then it's easy to see that: +// g(n+1) = f(n) + 3g(n) +// h(n+1) = f(n) + h(n) +// Initial values are h(1) = 1 and g(1) = 1. + +constexpr size_t mod{1000000007}; +constexpr size_t maxn{1000001}; +std::vector f(maxn); +std::vector g(maxn); +std::vector h(maxn); + +int main() { + g[1] = h[1] = 1; + f[1] = 2; + for (size_t i = 2; i < maxn; i++) { + g[i] = (f[i-1] + 3*g[i-1]) % mod; + h[i] = (f[i-1] + h[i-1]) % mod; + f[i] = (g[i] + h[i]) % mod; + } + + size_t t; + std::cin >> t; + for (size_t i = 0; i < t; i++) { + size_t n; + std::cin >> n; + std::cout << f[n] << "\n"; + } +} -- cgit v1.3