1
#include<stdio.h>
2
#define Max_N 1000000000
3
#define M 100000000
4
int A[2][2]={1,1,1,0};
5
int kb[32];
6
int 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
}
14
void 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
}
27
int 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
}
37
int 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 阅读(174)
评论(1) 编辑 收藏 引用 所属分类:
acm