COJ 0200 Fibonacci

전송 문: http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=200

시험 문제 설명:
지구 인 들 은 모두 Fibonicca 수열 을 안다.
1 1 2 3 5 8 -----
정정 수 L, R, 출력 피 보 니 카 수열 L 항 을 두 번 째 R 항 에 추가 한 결 과 를 입력 하 십시오. 답 이 많 을 수 있 으 므 로 답 의 뒷 7 자 리 를 출력 하 십시오.
입력:
첫 번 째 행 위 는 두 개의 정수 L, R.
출력:
출력 답안 의 뒷 7 자리 (전도 0 을 보류 하지 않 음)
예제 입력:
1 5
출력 예시:
12
기타 설명:
60% 데이터: 1 < = L < = R < = 1000000100% 데이터: 1 < = L < = R < = 2 ^ 31 - 1 중 20% 데이터 보증 L = R
문제 풀이: 접두사 와 사상: f (L, R) = f (1, R) - f (1, L), 그리고 누 드 매트릭스 곱 하기.
                                            [0 , 1 , 0]
[f(n-2),f(n-1),S(n-2)] * [1 , 1 , 1] = [f(n-1),f(n),S(n-1)]
                                            [0 , 0 , 1]
주의 n = 1, 2 특 판.

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 const int mod=10000000;
 8 struct Matrix{
 9     long long A[3][3];
10     Matrix(){memset(A,0,sizeof(A));}
11 };
12 void print(Matrix M){
13     for(int i=0;i<3;i++){
14         for(int j=0;j<3;j++) printf("%d ",M.A[i][j]);
15         puts("");
16     }puts("");return;
17 }
18 Matrix mul(Matrix a,Matrix b){
19     Matrix ans;
20     for(int i=0;i<3;i++)
21        for(int j=0;j<3;j++){
22            for(int k=0;k<3;k++) ans.A[i][j]+=a.A[i][k]*b.A[k][j];
23             ans.A[i][j]%=mod;
24         }
25     return ans;
26 }
27 Matrix pow(Matrix a,int n){
28     Matrix ans=a,tmp=a;n--;
29     while(n){
30         if(n&1) ans=mul(ans,tmp);
31         tmp=mul(tmp,tmp);
32         n>>=1;
33     } return ans;
34 }
35 inline int read(){
36     int x=0,sig=1;char ch=getchar();
37     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
38     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
39     return x*=sig;
40 }
41 inline void write(int x){
42     if(x==0){putchar('0');return;} if(x<0) putchar('-'),x=-x;
43     int len=0,buf[15]; while(x) buf[len++]=x%10,x/=10;
44     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
45 }
46 int initn[3][3]={
47     {0,1,0},
48     {1,1,1},
49     {0,0,1}
50 };
51 int solve(int n){
52     if(n==0) return 0;
53     if(n==1) return 1;//  ！ 
54     Matrix M;
55     for(int i=0;i<3;i++)
56         for(int j=0;j<3;j++)
57             M.A[i][j]=initn[i][j];
58             
59     M=pow(M,n-1);
60     //puts("here!");print(M);
61     return (M.A[1][1]+M.A[1][2])%mod;
62 }
63 
64 void init(){
65     return;
66 }
67 void work(){
68     int a=read(),b=read();
69     printf("%d
",(solve(b)-solve(a-1)+mod)%mod);
70     return;
71 }
72 void print(){
73     return;
74 }
75 int main(){
76     init();work();print();return 0;
77 }