题意

• 每天可以从三家店中选一家，不能连续三天选同一家，t次询问，每次询问连续选n天有多少种不同的选择方案

思路

• 简单动态规划，显然第i天的可选择方案数取决于第i-1和第i-2天
• 对于任意一个店，第i天可以选它的情况是
  • 第i-1天选另外两家，不用考虑第i-2天
  • 第i-1天选它，第i-2天只能选另外两家
• 综上,

AC代码

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
vector<long long> dp(101010);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    dp[1]=3;dp[2]=9;
    for(int i=3;i<101010;i++)
        dp[i]=(dp[i-1]+dp[i-2])*2%mod;
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        cout << dp[n] << endl;
    }
    return 0;
}