24 544984352

一开始，尽力想了，但是发现不会递推

然后看了题解，才秒懂。。。只能说太抽象了，

但又感觉很实际，就是一定得找到最后的要求是什么，需要什么。

第 i 天有多少种方案。

令dp[i] 为第i天有多少种不同方案。

跟第i – 1 天有关，如果第i  天是 1 ，如果第i-1天是0，或者2肯定可以满足条件

如果第i-1天是1，由不能连续三天是同一个数字，所以i – 2天一定得是0或者2.

得到状态转移方程：

dp[i – 1] 为 第i-1天有多少种不同方案，那第i天选择1 或者 2 或者 3 就有不同情况了

然后构成状态转移方程式，参考分类计数原理和分步计数原理。

dp[i] = dp[i-1] * 2 + dp[i-2] * 2;

 

 

//————————-代码—————————-

#define int LL
const int N = 1e6+10;
int n,m;
int p[N];
int inf = 1e9+7;
void solve()
{
     cin>>n;
//     V<V<int>>mp(n+1,V<int>(m+1));
     cout<<p[n]<<endl;
}

void pre() {
    
    p[1] = 3;
    p[2] = 9;
    fo(i,3,100000) {
        p[i] = 2 * (p[i-1] + p[i-2] + inf) % inf;
    }
}

signed main(){
    clapping();TLE;
    pre();
    int t;cin>>t;while(t — )
    solve();
//    {solve(); }
    return 0;
}

/*样例区

*/

//————————————————————

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。