题目链接： http://codeforces.com/gym/101061/problem/B
分析： 叨逼叨：(又是死在数学题上，这次一来就把式子合并去算递推公式去了，真是分分钟切腹自尽的节奏，又废了3个小时，下次看到数学题还是先从最初始的公式开始推，一个方向不行就换个方向，不要死磕一种方法！！！！） 题意： 种下1朵红花，1朵绿花，1朵蓝花； 一朵红花一晚上后变成1朵红花，2朵绿花，3朵蓝花， 一朵绿化一晚上后变成4朵红花，5朵绿花，6朵蓝花， 一朵蓝花一晚上后变成7朵红花，8朵绿花，9朵蓝花
求N天后一共多少朵花
题解： 由题意可以得出三个式子： ai=1ai−1+2bi−1+3ci−1 bi=4ai−1+5bi−1+6ci−1 ci=7ai−1+8bi−1+9ci−1
所以可以推出:
⎡⎣⎢⎢aibici⎤⎦⎥⎥=⎡⎣⎢⎢147258369⎤⎦⎥⎥∗⎡⎣⎢⎢ai−1bi−1ci−1⎤⎦⎥⎥
这样不断递推可以得出： ⎡⎣⎢⎢anbncn⎤⎦⎥⎥=⎡⎣⎢⎢147258369⎤⎦⎥⎥n
AC代码：
/************************************************************************* > File Name: B.cpp > Author: Akira > Mail: qaq.febr2.qaq@gmail.com > Created Time: 2016年08月13日 星期六 12时45分23秒 ************************************************************************/ #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <map> #include <cmath> #include <vector> #include <set> #include <list> #include <ctime> typedef long long LL; typedef unsigned long long ULL; typedef long double LD; #define MST(a,b) memset(a,b,sizeof(a)) #define CLR(a) MST(a,0) #define Sqr(a) ((a)*(a)) using namespace std; #define MaxN 100000 #define MaxM MaxN*10 #define INF 1000000000 const int mod = 1000000007; int n; struct Mat { LL mat[3][3]; }one; Mat operator*(Mat a,Mat b) { Mat c; CLR(c.mat); for(int k=0;k<3;k++) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { c.mat[i][j] += a.mat[i][k]%mod * b.mat[k][j]%mod; } } } return c; } Mat operator^ (Mat a, LL k) { Mat c; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { c.mat[i][j] = (i==j); } } for(;k;k>>=1) { if(k&1) c = c*a; a = a*a; } return c; } void init() { int cnt =1; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { one.mat[i][j] = cnt++; } } } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d", &n); if(n == 1) { cout << 3 << endl; continue; } init(); Mat N = one^(n-1); LL ans = 0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { ans += N.mat[i][j]; ans %= mod; } } cout << ans << endl; } }