1 /* 2 注意：矩阵快速幂是把构造的矩阵乘^n次（根据同余原理，计算中是可以%的）后，再与原矩阵想乘，把原矩阵做n次快速幂是错误的*/ 3 /* 4 联系一下int的快速幂： 5 ans=1； 6 while（n）//求b^n 7 { 8      if（n&1） 9       ans=ans*b；-------110     n>>=1;11     b=b*b;---------212 }13 就是把1,2两句中的相乘都用“三变量法”来做（矩阵的特殊性，不能把结果直接存进原矩阵中）。14 */

 1 #include<iostream> 2 using namespace std; 3 #include<cstdio> 4 typedef long long ll; 5 ll n,m; 6 ll p,q,a1,a2; 7 ll jz[3][3],b[3][3],c[3][3];/*注意以后遇到ll与int相乘的题目，把int的变量直接设为ll*/ 8 int main() 9 {10     cin>>p>>q>>a1>>a2;11     cin>>n>>m;n-=2;12     b[1][1]=jz[1][1]=0;b[1][2]=jz[1][2]=q;13     b[2][1]=jz[2][1]=1;b[2][2]=jz[2][2]=p;14     15     while(n)16     {17         if(n&1)18         {19             for(int i=1;i<=2;++i)20               for(int j=1;j<=2;++j)21                 for(int k=1;k<=2;++k)22                 c[i][j]=(c[i][j]+jz[i][k]*b[k][j]%m)%m;23             for(int i=1;i<=2;++i)24               for(int j=1;j<=2;++j)25               jz[i][j]=c[i][j],c[i][j]=0;26         }27         n>>=1;28         for(int i=1;i<=2;++i)29           for(int j=1;j<=2;++j)30             for(int k=1;k<=2;++k)31             c[i][j]=(c[i][j]+b[i][k]*b[k][j]%m)%m;32         for(int i=1;i<=2;++i)33           for(int j=1;j<=2;++j)34           b[i][j]=c[i][j],c[i][j]=0;35     }36     37     38     cout<<(a2*jz[2][1]%m+a1*jz[1][1]%m)%m;/*注意这里要把a1，a2乘以原来的那个01向量，而不是pq向量，因为矩阵计算了n-2次，如果乘以pq向量的话，计算出的是an+1*/39     return 0;40 }