1369D - TediousLee - CodeForces Solution

#include <iostream>
#include <vector>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int count = 0;
  std::cin >> count;

  const int k_max_level = 2 * 1e6 + 1;
  const int64_t k_value_mod = 1e9 + 7;
  std::vector<int64_t> crazy_tree_count(k_max_level, 0);
  std::vector<bool> head_use(k_max_level, false);
  crazy_tree_count[3] = 4;
  head_use[3] = true;
  for (int level = 4; level < k_max_level; ++level) {
    crazy_tree_count[level] =
        2 * crazy_tree_count[level - 2] + crazy_tree_count[level - 1];
    if (!head_use[level - 1] && !head_use[level - 2]) {
      head_use[level] = true;
      crazy_tree_count[level] += 4;
    }
    crazy_tree_count[level] %= k_value_mod;
  }

  for (int index = 0; index < count; ++index) {
    int level;
    std::cin >> level;
    std::cout << crazy_tree_count[level] << std::endl;
  }

  return 0;
}