1
#include<stdio.h>
2#define Max_N 1000000000
3#define M 100000000
4int A[2][2]={1,1,1,0};
5int kb[32];
6int D_to_B(int k)
7{
8 int i=0;
9 while(k>=1){
10 kb[i++]=k%2;
11 k/=2;}
12 return i;
13}
14void Multi(int a[2][2],int b[2][2])
15{
16 int i,j,k;
17 int temp[2][2]={0,0,0,0};
18 for(i=0;i<2;i++)
19 for(j=0;j<2;j++)
20 for(k=0;k<2;k++){
21 temp[i][j]+=int((__int64(a[i][k])*b[k][j])%M);
22 temp[i][j]%=M;}
23 for(i=0;i<2;i++)
24 for(j=0;j<2;j++)
25 a[i][j]=temp[i][j];
26}
27int Matrix_Multi(int a[2][2],int k)//a^k
28{
29 int t,i;
30 int temp[2][2]={1,0,0,1};
31 t=D_to_B(k);
32 for(i=t-1;i>=0;i--){
33 Multi(temp,temp);
34 if(kb[i]==1)Multi(temp,a);}
35 return (M+temp[0][0]-1)%M;
36}
37int main()
38{
39 int N,result;
40 while(scanf("%d",&N)!=EOF){
41 result=Matrix_Multi(A,N+1);
42 printf("%d\n",result);
43 }
44 return 0;
45}
posted on 2008-03-06 22:19
zoyi 閱讀(190)
評論(1) 編輯 收藏 引用 所屬分類:
acm