?

思路：题目难点就是找矩阵。。。。。

?

code:

?

#include
  
   
#include
   
     #include
    
      using namespace std; typedef long long LL; struct Matrix { LL x[5][5]; friend Matrix operator*(Matrix &a,Matrix &b); friend Matrix operator*(Matrix a,LL k); }; int n,mod; Matrix operator*(Matrix &a,Matrix &b) { Matrix c; int i,j,k; for(i=1;i<=3;i++) { for(j=1;j<=3;j++) { c.x[i][j]=0; for(k=1;k<=3;k++) { c.x[i][j]=(c.x[i][j]+(a.x[i][k]*b.x[k][j])%mod)%mod; } } } return c; } Matrix operator^(Matrix a,LL k) { Matrix unit; memset(unit.x,0,sizeof(unit.x)); for(int i=0;i<=3;i++) { unit.x[i][i]=1; } while(k>0) { if(k&1) unit=unit*a; a=a*a; k=k/2; //printf(AAAAA ); } return unit; } Matrix A,B; int main() { while(scanf(%d%d,&n,&mod)==2) { memset(A.x,0,sizeof(A.x)); A.x[1][2]=2,A.x[2][1]=1,A.x[2][2]=1; A.x[3][2]=A.x[3][3]=1; B.x[1][1]=1%mod; B.x[1][2]=2%mod; B.x[1][3]=1; if(n==1) printf(%lld ,B.x[1][1]); else if(n==2) { printf(%lld ,B.x[1][2]); } else { A=A^(n-2); B=B*A; printf(%lld ,B.x[1][2]%mod); } } return 0; } 
    
   
  

?