Problem 1683 纪念SlingShot Accept: 561 Submit: 1969
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
已知 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。
Input
第一行是一整数m，代表总共有m个cases。
Output
对于每个case，输出一行。格式见样例，冒号后有一个空格。
Sample Input
2
3
6
Sample Output
Case 1: 37
Case 2: 313
Source
FOJ月赛-2009年2月- Coral F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3）
设S(n)=F(0)+F(1)+ ... +F(n)
又有，S(n)=S(n-1)+F(n)，得到下面矩阵。
即，
使用矩阵快速幂运算计算结果。
1 #include <iostream> 2 #include <algorithm> 3 #include <map> 4 #include <vector> 5 #include <functional> 6 #include <string> 7 #include <cstring> 8 #include <queue> 9 #include <set> 10 #include <cmath> 11 #include <cstdio> 12 using namespace std; 13 #define IOS ios_base::sync_with_stdio(false)] 14 typedef long long LL; 15 const int INF=0x3f3f3f3f; 16 17 const int modnum=2009; 18 const int maxn=5; 19 typedef struct matrix{ 20 int v[maxn][maxn]; 21 void init(){memset(v,0,sizeof(v));} 22 }M; 23 M a,b; 24 M mul_mod(const M &a,const M &b,int L,int m,int n) 25 { 26 M c; c.init(); 27 for(int i=0;i<L;i++){ 28 for(int j=0;j<n;j++){ 29 for(int k=0;k<m;k++)//注意j，k范围 30 c.v[i][j]=(c.v[i][j]+(a.v[i][k]*b.v[k][j]%modnum))%modnum; 31 } 32 } 33 return c; 34 } 35 M power(M x,int L,int p) 36 { 37 M tmp; tmp.init(); 38 for(int i=0;i<L;i++) 39 tmp.v[i][i]=1; 40 while(p){ 41 if(p&1) tmp=mul_mod(x,tmp,L,L,L); 42 x=mul_mod(x,x,L,L,L); 43 p>>=1; 44 } 45 return tmp; 46 } 47 void init() 48 { 49 a.init(); 50 a.v[0][0]=1; 51 a.v[0][1]=a.v[1][1]=3; 52 a.v[0][2]=a.v[1][2]=2; 53 a.v[0][3]=a.v[1][3]=7; 54 a.v[2][1]=a.v[3][2]=1; 55 b.init(); 56 b.v[0][0]=9; 57 b.v[1][0]=5; 58 b.v[2][0]=3; 59 b.v[3][0]=1; 60 } 61 int main() 62 { 63 int m,n,ca=0; 64 scanf("%d",&m); 65 while(m--){ 66 scanf("%d",&n); 67 init(); 68 if(n<3){printf("Case %d: %d ",++ca,b.v[3-n][0]); continue;} 69 a=power(a,4,n-2); 70 a=mul_mod(a,b,4,4,1); 71 printf("Case %d: %d ",++ca,a.v[0][0]); 72 } 73 }