Torni

input/code.cpp: In function 'int main()':
input/code.cpp:15:49: warning: iteration 101010 invokes undefined behavior [-Waggressive-loop-optimizations]
         for(int i = 0; i < 1010101; i++) dp2[i] = 0;
                                          ~~~~~~~^~~
input/code.cpp:15:26: note: within this loop
         for(int i = 0; i < 1010101; i++) dp2[i] = 0;
                        ~~^~~~~~~~~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll big = 1e9+7;
ll dp[1010101];
ll dp2[101010];
int main(){
    ll t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        for(int i = 0; i < 1010101; i++) dp[i] = 0;
        for(int i = 0; i < 1010101; i++) dp2[i] = 0;
        dp[1] = 1;
        dp2[1] = 1;
        for(int i = 2; i <= n; i++){
            dp2[i] = 4*dp2[i-1] + dp[i-1];
            dp[i] = dp2[i-1] + 2*dp[i-1];
            dp2[i] %= big;
            dp[i] %= big;
        }
        cout << (dp[n] + dp2[n])%big << "\n";
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED