Poor God Water

Poor God Water

【题意】

​ 主人公God Water喜欢吃肉,鱼和巧克力。但是对于God Water来说,连续三个小时如果乱吃吃东西会有危险。题目给出食物中毒的情况分为三种。

1、连续三个小时吃同一样食物

2、如果连续三个小时吃都吃了不同的食物,而又巧克力在中间。

3、如果前后两个小时都吃了巧克力,而中间吃的是其他东西。

给出n个小时,主人公God Water能在这n个小时吃东西的方案数为多少?

【题解】

设肉,巧克力,鱼分别为A,B和C。

根据上述情况,连续三个小时会中毒的情况分别为:

1、AAA,BBB,CCC

2、ABC,CBA

3、BAB,BCB

首先我们可以得知,
n=1时,输出3。
n=2时,输出9。

当n=3时,就排除上述的7种情况,就应为20种方案。

相当于进行一次递推,递推的过程中。
对于每次推导的过程中,我们只关心最后两位,前n-2位并不关心,前n-2位已经是正确的方案推导出来的。相当于在在其后面添加A,B,C。

所以,当n=4时,其实就相当于在n=3的20种情况下,在后面添加A,B,C。
以此类推,利用矩阵快速幂来解决。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
typedef struct Matrix{
    ll mat[9][9];
}Mat;
Mat qmul( Matrix &a,Matrix &b ){
    Mat c ;
    for(int i=0;i<9;i++){
        for(int k=0;k<9;k++){
            c.mat[i][k] = 0;
            for(int j=0;j<9;j++){
                c.mat[i][k] = (c.mat[i][k]+a.mat[i][j]*b.mat[j][k])%mod;
            }
        }
    }
    return c ;
}
Mat qpow(Mat &a,ll b){
    Mat c ;
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
           c.mat[i][j] = (i==j);
        }
    }

    while( b ){
        if( b&1 ){
            c = qmul(c,a);
        }
        a = qmul(a,a);
        b >>=1 ;
    }
    return c ;
}
int A[9][9] = {

    0,0,0,1,0,0,1,0,0,
    1,0,0,0,0,0,1,0,0,
    1,0,0,1,0,0,1,0,0,

    0,1,0,0,1,0,0,0,0,
    0,1,0,0,0,0,0,1,0,
    0,0,0,0,1,0,0,1,0,

    0,0,1,0,0,1,0,0,1,
    0,0,1,0,0,0,0,0,1,
    0,0,1,0,0,1,0,0,0
};
int main()
{
    int T;
    for ( scanf("%d",&T); T ;T--){
        ll n;
        scanf("%lld",&n);
        if( n==1 ){ printf("3\n");}
        else if( n==2 ){ printf("9\n");}
        else{
            Mat a,b;
            ll ans = 0 ;
            for(int i=0;i<9;i++) for(int j=0;j<9;j++)
                a.mat[i][j] = A[i][j];
            b = qpow(a,n-2);
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    ans = ( ans + b.mat[i][j] )%mod ;
                }
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}