counting_towers_2413.cpp (957B)
1 #include <iostream> 2 #include <vector> 3 4 // Recurrence relation: 5 // f(n) = sum over i from 0 to n-1 of f(i) * p(n-i) 6 // where p(n) is the number of indivisible towers of height n, 7 // which is easily seen to be 3^(n-1)+1. 8 // Then we can expand: 9 // f(n) = sum_{i=0}^{n-1} f(i)(3^{n-i-1}+1) = g(n) + h(n) 10 // where we define g(n) = sum f(i)3^{n-i-1} and h(n) = sum f(i). 11 // Then it's easy to see that: 12 // g(n+1) = f(n) + 3g(n) 13 // h(n+1) = f(n) + h(n) 14 // Initial values are h(1) = 1 and g(1) = 1. 15 16 constexpr size_t mod{1000000007}; 17 constexpr size_t maxn{1000001}; 18 std::vector<size_t> f(maxn); 19 std::vector<size_t> g(maxn); 20 std::vector<size_t> h(maxn); 21 22 int main() { 23 g[1] = h[1] = 1; 24 f[1] = 2; 25 for (size_t i = 2; i < maxn; i++) { 26 g[i] = (f[i-1] + 3*g[i-1]) % mod; 27 h[i] = (f[i-1] + h[i-1]) % mod; 28 f[i] = (g[i] + h[i]) % mod; 29 } 30 31 size_t t; 32 std::cin >> t; 33 for (size_t i = 0; i < t; i++) { 34 size_t n; 35 std::cin >> n; 36 std::cout << f[n] << "\n"; 37 } 38 }