原题： ?pid=1005
题目大意： 按规律求出第n项。 由矩阵乘法我们可以知道：
所以对于fib数列我们可以用矩阵来求，，由于矩阵可以左乘右乘，所以我们可以用快速幂来优化。
;const int bc=2;const int mod = 7;struct matrix{int x[bc][bc];};matrix mutimatrix(matrix a,matrix b){matrix temp;memset(temp.x,0,sizeof(temp.x));for(int i=0;i<bc;i++) //答案的行{for(int j=0;j<bc;j++) //答案的列{for(int k=0;k<bc;k++){temp.x[i][j]+=a.x[i][k]*b.x[k][j];temp.x[i][j]%=mod;}}}return temp;}matrix powmatrix(matrix a,int b){matrix temp;memset(temp.x,0,sizeof(temp.x));//初始化矩阵为单位阵for(int i=0;i<bc;i++)temp.x[i][i]=1;while(b){if(b%2==1)temp=mutimatrix(temp,a);a=mutimatrix(a,a);b=b/2;}return temp;}int main(){int a,b,n;//freopen(“in.txt”,”r”,stdin);while(scanf(“%d %d %d”,&a,&b,&n)!=EOF){if(a==0&&b==0&&n==0) break;matrix st;//因为每次都是a个F(n-1)和b个F(n-2)相加，所以这里如此初始化//Fib数列这里就直接单位阵st.x[0][0]=a;st.x[0][1]=1;st.x[1][0]=b;st.x[1][1]=0;st=powmatrix(st,n-1);printf(“%d\n”,(st.x[0][1]+st.x[1][1])%mod);}return 0;}
于是渐渐开始有些伤怀。
