Poor God Water
時間限制: 1 Sec 內存限制: 128 MB
提交: 102 解決: 50
[提交] [狀態] [命題人:admin]
題目描述
God Water likes to eat meat, fish and chocolate very much, but unfortunately, the doctor tells him that some sequence of eating will make them poisonous.
Every hour, God Water will eat one kind of food among meat, fish and chocolate. If there are 3 continuous hours when he eats only one kind of food, he will be unhappy. Besides, if there are 3 continuous hours when he eats all kinds of those, with chocolate at the middle hour, it will be dangerous. Moreover, if there are 3 continuous hours when he eats meat or fish at the middle hour, with chocolate at other two hours, it will also be dangerous.
Now, you are the doctor. Can you find out how many different kinds of diet that can make God Water happy and safe during N hours? Two kinds of diet are considered the same if they share the same kind of food at the same hour. The answer may be very large, so you only need to give out the answer module 1000000007.

輸入
The fist line puts an integer T that shows the number of test cases. (T≤1000)
Each of the next T lines contains an integer N that shows the number of hours. (1≤N≤10^10)

輸出
For each test case, output a single line containing the answer.

樣例輸入
復制樣例數據
3
3
4
15
樣例輸出
20
46
435170

題目大意：
假設魚為$a$，肉為$b$，巧克力為$c$，先輸入一個數字$T$，表示共有$T$組測試數據，下面$T$行每行輸入一個整數$n$，代表有$n$個時刻，每個時刻可以吃一種食物，但不能連續三個小時吃同一種食物，即$aaa$，$bbb$，$ccc$不合法，當在三個小時內三種食物都吃的話，巧克力不能放中間，即$acb$，$bca$不合法，還有就是$cac$，$bcb$，問共有多少種吃法。

解題思路：
當$n=1$時，有$f[1]=3$種吃法，即$a,b,c$
當$n=2$時，有$f[2]=9$種吃法，并假設
$1、aa2、ba3、ca$
$4、ab5、bb6、cb$
$7、ac8、bc9、cc$
當$n=3$時，有$f[3]=20$種吃法
$1、aa\{\begin{array}{l}b\\ c\end{array}2、ba?\begin{array}{l}a\\ b\\ c\end{array}3、ca\{\begin{array}{l}a\\ b\end{array}$
$4、ab?\begin{array}{l}a\\ b\\ c\end{array}5、bb\{\begin{array}{l}a\\ c\end{array}6、cb\{\begin{array}{l}a\\ b\end{array}$
$7、ac\{\begin{array}{l}a\\ c\end{array}8、bc\{\begin{array}{l}b\\ c\end{array}9、cc\{\begin{array}{l}a\\ b\end{array}$
當$n>=3$時
其情況$1$的個數有：$f[n?1].2+f[n?1].3$
其情況$2$的個數有：$f[n?1].4+f[n?1].5+f[n?1].6$
其情況$3$的個數有：$f[n?1].7+f[n?1].9$
其情況$4$的個數有：$f[n?1].1+f[n?1].2+f[n?1].3$
其情況$5$的個數有：$f[n?1].4+f[n?1].6$
其情況$6$的個數有：$f[n?1].8+f[n?1].9$
其情況$7$的個數有：$f[n?1].1+f[n?1].2$
其情況$8$的個數有：$f[n?1].4+f[n?1].5$
其情況$9$的個數有：$f[n?1].7+f[n?1].8$
所以可得：
$\left|\begin{array}{ccccccccc}f[n].1& f[n].2& f[n].3& f[n].4& f[n].5& f[n].6& f[n].7& f[n].8& f[n].9\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right|=\left|\begin{array}{ccccccccc}1& 1& 1& 1& 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right|\times {\left|\begin{array}{ccccccccc}0& 0& 0& 1& 0& 0& 1& 0& 0\\ 1& 0& 0& 1& 0& 0& 1& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 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& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 1& 0& 0& 1& 0& 0& 0\end{array}\right|}^{n?2}$
因此直接用矩陣快速冪計算即可

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
struct node
{ll arr[9][9];node() {ms(arr);}
};
node mul(node a,node b) {node c;for(int i=0;i<9;i++) {for(int j=0;j<9;j++) {for(int k=0;k<9;k++) {c.arr[i][j]=(c.arr[i][j]+(a.arr[i][k]*b.arr[k][j])%mod+mod)%mod;}}}return c;
}
ll quickpow(ll n) {node base;base.arr[1][0]=1;base.arr[2][0]=1;base.arr[3][1]=1;base.arr[4][1]=1;base.arr[5][1]=1;base.arr[6][2]=1;base.arr[8][2]=1;base.arr[0][3]=1;base.arr[1][3]=1;base.arr[2][3]=1;base.arr[3][4]=1;base.arr[5][4]=1;base.arr[7][5]=1;base.arr[8][5]=1;base.arr[0][6]=1;base.arr[1][6]=1;base.arr[3][7]=1;base.arr[4][7]=1;base.arr[6][8]=1;base.arr[7][8]=1;node a;a.arr[0][0]=1;a.arr[0][1]=1;a.arr[0][2]=1;a.arr[0][3]=1;a.arr[0][4]=1;a.arr[0][5]=1;a.arr[0][6]=1;a.arr[0][7]=1;a.arr[0][8]=1;while(n) {if(n&1) a=mul(a,base);base=mul(base,base);n>>=1;}ll ans=0;for(int i=0;i<9;i++) {ans=(ans+a.arr[0][i])%mod;}return ans;
}
int main() 
{#ifndef ONLINE_JUDGE//freopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int T;scanf("%d",&T);while(T--) {ll n;scanf("%lld",&n);if(n==1) printf("3\n");else printf("%lld\n",quickpow(n-2));}return 0;
}