斐波那契数列的定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …)
给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。
Input
输入1个数n(1 <= n <= 10^18)。
Output
输出F(n) % 1000000009的结果。
Input示例
11
Output示例
89
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
|
#define mod 1000000009
struct {
long long int c[2][2];
} t;
long long int n;
node mul(node a,node b){
node c;
int i,j,k;
for(i=0;i<2;i++){
for(j=0;j<2;j++){
c.c[i][j]=0;
for(k=0;k<2;k++)
c.c[i][j]+=(a.c[i][k]*b.c[k][j])%mod;
c.c[i][j]=c.c[i][j]%mod;
}
}
return c;
}
node kuaisumi(long long int n){
node res = t;
if(n<0)
return res;
while(n){
if(n&1)
res=mul(res,t);
t=mul(t,t);
n=n>>1;
}
return res;
}
int main(){
while(~scanf("%lld",&n)){
t.c[0][0] = 1;
t.c[0][1] = 1;
t.c[1][0] = 1;
t.c[1][1] = 0;
node res=kuaisumi(n-2);
printf("%lldn",res.c[0][0]);
}
}
|
近期评论