建议做矩阵相乘时先做3070,后面在开始做3233,3623,2440.3623和2440我还没开始做，今天下午就要自己做出来！！！！还有。。。海贼王更新了！！！！
1 #include<iostream>
2 using namespace std;
3 //===================================================
4 int k;
5 struct Point
6 {
7 int a[2][2];
8 void init()
9 {
10 a[0][0]=1;a[0][1]=1;
11 a[1][0]=1;a[1][1]=0;
12 }
13 };
14
15 Point mul(Point p,Point q)//矩阵相乘
16 {
17 int i,j;
18 Point c;
19 for(i=0;i<2;++i)
20 {
21 for(int j=0;j<2;++j)
22 {
23 int sum=0;
24 for(int k=0;k<2;++k)
25 {
26 sum+=(p.a[i][k]*q.a[k][j])%10000;
27 /* if(sum>10000)
28 {
29 sum-=10000;
30 }*/
31 c.a[i][j]=sum%10000;
32 }
33 }
34 }
35 return c;
36 }
37
38 Point maxtrimul(Point s,int k)
39 {
40 Point ans;
41 ans=s;
42 if(k==1)return s;
43 ans=maxtrimul(s,k>>1);
44 ans=mul(ans,ans);
45 if(k&1)
46 {
47 ans=mul(s,ans);//切记！！！！
48 }
49 return ans;
50
51
52 }
53
54 int main()
55 {
56 Point s;
57 s.init();
58 Point c;
59 while(cin>>k&&k!=-1)
60 {
61 if(k==0)
62 {
63 cout<<0<<endl;
64 continue;
65 }
66 if(k==1)
67 {
68 cout<<1<<endl;
69 continue;
70 }
71 c=maxtrimul(s,k);
72 cout<<(c.a[0][1]%10000)<<endl;
73 continue;
74
75 }
76 }