Torni

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;

ll modPow(ll a, ll b) {
	if (b & 1) return a * modPow(a, b-1) % MOD;
	if (b == 0) return 1;
	return modPow(a*a % MOD, b / 2);
}

const int N = 1e6;
ll pref1[N+1]; // Count if starts with two 1-wide pieces
ll pref2[N+1]; // Count if starts with one 2-wide piece
ll ans[N+1];

void solve() {
	int n;
	cin >> n;
	cout << ans[n] << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	// DP1[n] = \sum_{i = 1}^{n} (2^{i} DP1[n-i] + 2^{i-1} DP2[n-i])
	// DP2[n] = \sum_{i = 1}^{n} DP1[n-i] + DP2[n-i]

	ll two_inv = modPow(2, MOD - 2);
	ll two_pow = 2, inv_pow = two_inv;

	pref1[0] = two_inv;
	pref2[0] = 1;
	ans[0] = 1;

	for (int i = 1; i <= N; ++i) {
		ll dp1 = (two_pow * pref1[i-1]) % MOD;
		ll dp2 = pref2[i-1];

		ll nxt_inv_pow = (inv_pow * two_inv) % MOD;
		pref1[i] = (pref1[i-1] + inv_pow * dp1 + nxt_inv_pow * dp2) % MOD;
		pref2[i] = (pref2[i-1] + dp1 + dp2) % MOD;
		ans[i] = (dp1 + dp2) % MOD;

		two_pow = (2 * two_pow) % MOD;
		inv_pow = nxt_inv_pow;
	}

	int t;
	cin >> t;
	for (int ti = 0; ti < t; ++ti) solve();
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED