FZU - 1683 紀念SlingShot 矩陣快速冪
題目大意：已知 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。
解題思路：借用別人的圖
![這裡寫圖片描述](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012112574541.jpg "\")
這題和HDU - 1757 A Simple Math Problem和相似，只不過這題多了個和，其實思路是差不多的<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwcmUgY2xhc3M9"brush:java;">
#include
#include
#define mod 2009
const int N = 4;
typedef long long 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;
}
