Read the program below carefully then answer the question.

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include<iostream>

#include <cstring>

#include <cmath>

#include <algorithm>

#include<vector>

const int MAX=100000*2;

const int INF=1e9;

int main()

{

  int n,m,ans,i;

  while(scanf("%d%d",&n,&m)!=EOF)

  {

    ans=0;

    for(i=1;i<=n;i++)

    {

      if(i&1)ans=(ans*2+1)%m;

      else ans=ans*2%m;

    }

    printf("%d\n",ans);

  }

  return 0;

}

矩阵快速幂

1 #include
      
        2 #include
       
         3 typedef long long ll; 4 int mod; 5 struct mat{ 6     int r,c; 7     ll m[5][5]; 8     void clear(){ 9         for(int i=1;i<=r;i++)memset(m[i],0,sizeof(m[i]));10     }11 };12 13 mat MatMul(mat m1,mat m2){14     mat tmp;15     tmp.r=m1.r;16     tmp.c=m2.c;17     int i,j,k;18     for(i=1;i<=tmp.r;i++){19         for(j=1;j<=tmp.c;j++){20             ll t=0;21             for(k=1;k<=m1.c;k++){22                 t=(t+(m1.m[i][k]*m2.m[k][j])%mod)%mod;23             }24             tmp.m[i][j]=t;25         }26     }27     return tmp;28 }29 30 mat MatQP(mat a,int n){31     mat ans,tmp=a;32     ans.r=ans.c=a.r;33     memset(ans.m,0,sizeof(ans.m));34     for(int i=1;i<=ans.r;i++){35         ans.m[i][i]=1;36     }37     while(n){38         if(n&1)ans=MatMul(ans,tmp);39         n>>=1;40         tmp=MatMul(tmp,tmp);41     }42     return ans;43 }44 45 int main(){46     mat a;47     a.r=3;a.c=1;48     a.m[1][1]=0;49     a.m[2][1]=1;50     a.m[3][1]=1;51     mat t;52     t.r=3;53     t.c=3;54     t.clear();55     t.m[1][1]=4;56     t.m[1][3]=2;57     t.m[2][1]=8;58     t.m[2][3]=5;59     t.m[3][3]=1;60     int n;61     while(scanf("%d%d",&n,&mod)!=EOF){62         mat tmp=MatQP(t,n/2);63         tmp=MatMul(tmp,a);64         printf("%lld\n",tmp.m[n%2+1][1]);65     }66     return 0;67 }