题目链接：

这个博客讲的比较好：http://blog.csdn.net/ljd4305/article/details/8987823

题意：给定a,b,,n,m,求Sn

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 using namespace std; 9 __int64 b,k,n,mod;10 struct matrix11 {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<