1 files changed, 38 insertions, 0 deletions

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 <iostream>
+#include <vector>
+
+// 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<size_t> f(maxn);
+std::vector<size_t> g(maxn);
+std::vector<size_t> 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";
+        }
+}