题目大意：已知 F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，，输出F（0）+ F（1）+ …… + F（n） mod 2009。
解题思路：借用别人的图
这题和HDU – 1757 A Simple Math Problem和相似，只不过这题多了个和，其实思路是差不多的
N = 4;ll;struct Matrix{ll mat[N][N];}a, b, tmp;int n;void init() {for(int i = 0; i < N; i++)for(int j = 0; j < N; j++)a.mat[i][j] = b.mat[i][j] = 0;for(int i = 0; i < N; i++)b.mat[i][i] = 1;a.mat[0][0] = a.mat[0][1] = a.mat[2][1] = a.mat[3][2] = 1;a.mat[1][1] = 3;a.mat[1][2] = 2;a.mat[1][3] = 7;}Matrix matrixMul(Matrix x, Matrix y) {for(int i = 0; i < N; i++)for(int j = 0; j < N; j++) {tmp.mat[i][j] = 0;for(int k = 0; k < N; k++)tmp.mat[i][j] += (x.mat[i][k] * y.mat[k][j]) % mod;}return tmp;}void solve() {while(n) {if(n & 1)b = matrixMul(b,a);a = matrixMul(a,a);n >>= 1;}}int main() {int test, cas = 1;scanf(“%d”, &test);while(test–) {scanf(“%d”, &n);init();if(n <= 2) {switch(n) {case 0:printf(“Case %d: 1\n”, cas++);break;case 1:printf(“Case %d: 4\n”);break;case 2:printf(“Case %d: 9\n”);break;}continue;}n -= 1;solve();printf(“Case %d: %lld\n”,cas++, (b.mat[0][0] * 4 + b.mat[0][1] * 5 + b.mat[0][2] * 3 + b.mat[0][3] * 1) % mod);}return 0;}
别人失去了信心，他却下决心实现自己的目标。
