题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4565
这个博客讲的比较好：http://blog.csdn.net/ljd4305/article/details/8987823
题意：给定a,b,,n,m,求Sn
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include<cmath> 6 #include<sstream> 7 #include<string> 8 using namespace std; 9 __int64 b,k,n,mod; 10 struct matrix 11 { 12 __int64 m[2][2]; 13 }; 14 matrix a,per,s,ans; 15 void init()//初始化操作 16 { 17 18 s.m[0][0]=((2*((k%mod)*(k%mod))%mod)%mod+(2*b)%mod)%mod; 19 s.m[0][1]=(2*(k%mod))%mod; 20 s.m[1][0]=0; 21 s.m[1][1]=0; 22 23 a.m[0][0]=(2*(k%mod))%mod; 24 a.m[0][1]=1; 25 a.m[1][0]=(((b%mod)-((k%mod)*(k%mod))%mod)+mod)%mod; 26 a.m[1][1]=0; 27 } 28 matrix mul(matrix x,matrix y) 29 { 30 matrix temp; 31 memset(temp.m,0,sizeof(temp.m)); 32 for(int i=0;i<2;i++) 33 for(int j=0;j<2;j++) 34 for(int k=0;k<2;k++) 35 temp.m[i][j]=(temp.m[i][j]+x.m[i][k]*y.m[k][j])%mod; 36 return temp; 37 } 38 matrix mpow(matrix A,__int64 n) 39 { 40 matrix B; 41 memset(B.m,0,sizeof(B.m)); 42 for(int i=0;i<2;i++) 43 B.m[i][i]=1; 44 while(n>0) 45 { 46 if(n&1) 47 B=mul(B,A); 48 A=mul(A,A); 49 n>>=1; 50 } 51 return B; 52 } 53 int main() 54 { 55 56 while(~scanf("%I64d%I64d%I64d%I64d",&k,&b,&n,&mod)) 57 { 58 init(); 59 if(n==1) 60 { 61 cout<<(2*(k%mod))%mod<<endl; 62 continue; 63 } 64 else if(n==2) 65 { 66 cout<<((2*(k%mod)*(k%mod))%mod+(2*(b%mod))%mod)%mod<<endl; 67 continue; 68 } 69 else 70 { 71 ans=mpow(a,n-2); 72 ans=mul(s,ans); 73 cout<<ans.m[0][0]<<endl; 74 } 75 } 76 return 0; 77 }