1005 矩陣快速冪

本體有2種方法，一種是矩陣快速冪，一種是找規律。我用的是矩陣快速冪。

f(1)=1; f(2)=1; f(n)=( A*(f(n-1)) + B*(f(n-2)) )mod7;

[ f(n)??? ]?? = [ A B ]? * [ f(n-1) ]????? =>????? [ f(n)??? ]? = [ A B ] (n-2）? * [ f(1) ]

[ f(n-1) ]????? [ 1 0 ]???? [ f(n-2) ]????? =>????? [ f(n-1) ]???? [ 1 0 ]?????????????? [ f(2)? ]

?

1 #include <stdio.h> 2 #include <iostream> 3 #include <cmath> 4 #include <string.h> 5 using namespace std; 6 struct matrix{ 7 int a[2][2]; 8 }res,temp; 9 matrix mul(matrix a,matrix b){ 10 matrix t; 11 memset(t.a,0,sizeof(t.a)); 12 int i,j,k; 13 for(i=0;i<2;++i) 14 for(j=0;j<2;++j) 15 for(k=0;k<2;++k){ 16 t.a[i][j]+=a.a[i][k]*b.a[k][j]; 17 t.a[i][j]%=7; 18 } 19 return t; 20 } 21 int main(){ 22 int A,B,n,i,j; 23 while(~scanf("%d%d%d",&A,&B,&n)){ 24 if(A==0&&B==0&&n==0) break; 25 if(n<=2) {printf("1\n");continue;} 26 27 memset(res.a,0,sizeof(res.a)); 28 res.a[0][0]=res.a[1][1]=1; 29 temp.a[0][0]=A; 30 temp.a[0][1]=B; 31 temp.a[1][0]=1; 32 temp.a[1][1]=0; 33 n=n-2; 34 while(n){ 35 if(n&1) 36 res=mul(res,temp); 37 n>>=1; 38 temp=mul(temp,temp); 39 } 40 printf("%d\n",(res.a[0][0]+res.a[0][1])%7 ); 41 } 42 43 return 0; 44 45 }

?

posted on 2013-09-03 11:22 symons 閱讀(...) 評論(...) 編輯 收藏

轉載于:https://www.cnblogs.com/symons1992/p/3298345.html

總結

以上是生活随笔為你收集整理的1005 矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。