传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=200
试题描述：
地球人都知道Fibonicca数列：
1 1 2 3 5 8 -----
输入两个正整数L，R，输出Fibonicca数列第L项加到第R项的结果，因为答案可能很大，请输出答案的后7位（不保留前导零）。
输入：
第一行为两个正整数L，R.
输出：
输出答案的后7位（不保留前导零）
输入示例：
1 5
输出示例：
12
其他说明：
60%数据: 1<=L<=R<=1000000
100%数据: 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 }