Torni

#include <iostream>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const int N_MAX = 1e6+10;
// dp1[i] == number of towers of length i starting with |___|
ll dp1[N_MAX];
// dp2[i] == number of towers of length i starting with |_|_|
ll dp2[N_MAX];
int main() {
  // sum{1 <= j <= i}(2^(2*(j-1))*dp1[i-j])
  ll dp1_sum = 1;
  // sum{1 <= j <= i}(2^(j-1)*dp2[i-j])
  ll dp2_sum = 1;
  for(int i = 1; i < N_MAX; ++i) {
    dp1[i] = dp2_sum;
    dp2[i] = dp1_sum;
 
    dp1_sum *= 4;
    dp1_sum += dp1[i];
    dp1_sum %= MOD;
 
    dp2_sum *= 2;
    dp2_sum += dp2[i];
    dp2_sum %= MOD;
  }
  int n;
  cin>>n;
  for(int i = 0; i < n; ++i) {
    int x;
    cin>>x;
    cout<<(dp1[x] + dp2[x])%MOD<<endl;
  }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED