纪念SlingShot

很多时候题目里面没有给你n的范围，所以把所有的情况都列出，没有列全的话也会出现time limit 的错误！！！

及时给了不明确，也要列出来

题意：f(0)=1,f(1)=3,f(2)=5,f(n)=3f(n-1)+2f(n-2)+5f(n-3)。求s(n)=(f(0)+f(1)……+f(n)) 09。

思路：S(n)=S(n-1)+F(n)=S(n-1)+3F(n-1)+2F(n-2)+7F(n-3)，因此构造矩阵：

 

G - 纪念S lingShot Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit  Status

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 #include <iostream> #include <cstdio> #include <cstring> #define mod 2009 using namespace std; struct matrix { int ma[5][5]; }; matrix mult(matrix a,matrix b) { matrix ans; memset(ans.ma,0,sizeof(ans.ma)); for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) { for(int k=1;k<=4;k++) { ans.ma[i][j]+=(a.ma[i][k]*b.ma[k][j])%mod; } ans.ma[i][j]%=mod; } } return ans; } matrix pow(matrix x,int n) { matrix ans; memset(ans.ma,0,sizeof(ans.ma)); for(int i=1;i<=4;i++) { ans.ma[i][i]=1; } while(n) { if(n&1) { ans=mult(ans,x); } x=mult(x,x); n>>=1; } return ans; } int main() { int n; int t; scanf("%d",&t); for(int cou=1;cou<=t;cou++) { scanf("%d",&n); if(n==1) { printf("Case %d: 4\n",cou); continue; } else if(n==2) { printf("Case %d: 9\n",cou); continue; } else if(n==0) { printf("Case %d: 1\n",cou); continue; } matrix x; memset(x.ma,0,sizeof(x.ma)); x.ma[1][1]=1,x.ma[1][2]=3,x.ma[1][3]=2,x.ma[1][4]=7; x.ma[2][1]=0,x.ma[2][2]=3,x.ma[2][3]=2,x.ma[2][4]=7; x.ma[3][1]=0,x.ma[3][2]=1,x.ma[3][3]=0,x.ma[3][4]=0; x.ma[4][1]=0,x.ma[4][2]=0,x.ma[4][3]=1,x.ma[4][4]=0; x=pow(x,n-2); int sum=(x.ma[1][2]*5)%mod+(x.ma[1][3]*3)%mod+(x.ma[1][4]*1)%mod+(x.ma[1][1]*9)%mod; printf("Case %d: %d\n",cou,sum%mod); } return 0; }