西电ACM1197——斐波那契数列

原题如下：

#include<stdio.h>#include<string.h>long long mt[10]={1,55,687995182,517691607,271496360,911435502,918091266,490189494,908460138,21};typedef struct Matrix{long long a[2][2];}Matrix;Matrix E;void InitE(int size) //初始化单位矩阵{for(int i=0;i<size;i++){for(int j=0;j<size;j++)E.a[i][j]=(i==j);}}Matrix MatrixMul(Matrix a,Matrix b) //两矩阵相乘 {Matrix c;int i,j,k;for(i=0;i<2;i++){for(j=0;j<2;j++){c.a[i][j]=0;for(k=0;k<2;k++){c.a[i][j] += ((a.a[i][k]%1000000007)*(b.a[k][j]%1000000007));c.a[i][j]%=1000000007;}}}return c;}Matrix MatrixPow(Matrix a,long long n) //矩阵快速二分求n次幂{Matrix t=E;while(n>0){if(1&n) //n是奇数t=MatrixMul(t,a);a=MatrixMul(a,a);n >>= 1;}return t;}int main(){long long n;int k,i;Matrix matrix,m;char num[100000];InitE(2);while(1){k=0;scanf("%s",&num);if(strcmp(num,"exit")==0)break;if(strcmp(num,"1")==0){//scanf("%I64d",&n);scanf("%lld",&n);if(n==1||n==2)printf("1\n");else{matrix.a[0][0]=1; //构造初始矩阵matrix.a[0][1]=1;matrix.a[1][0]=1;matrix.a[1][1]=0;m=MatrixPow(matrix,n-1);printf("%lld\n",(m.a[0][0])%1000000007);}for(i=0;i<10;i++)printf("-");printf("\n");}else if(strcmp(num,"2")==0){for(i=0;i<10;i++)printf("%lld\n",mt[i]);for(i=0;i<10;i++)printf("-");printf("\n");}else{for(i=0;i<strlen(num);i++){int c=num[i]-'0';if((c<0)||(c>9)){k=1;break;}}if(k==1){printf("error\n");for(i=0;i<10;i++) printf("-"); printf("\n");}else{printf("none\n");for(i=0;i<10;i++) printf("-"); printf("\n");}}}return 0;}