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;
}
矩阵快速幂
#include<stdio.h>
#include<string.h>
typedef long long ll;
int mod;
struct mat{
int r,c;
ll m[][];
void clear(){
for(int i=;i<=r;i++)memset(m[i],,sizeof(m[i]));
}
}; mat MatMul(mat m1,mat m2){
mat tmp;
tmp.r=m1.r;
tmp.c=m2.c;
int i,j,k;
for(i=;i<=tmp.r;i++){
for(j=;j<=tmp.c;j++){
ll t=;
for(k=;k<=m1.c;k++){
t=(t+(m1.m[i][k]*m2.m[k][j])%mod)%mod;
}
tmp.m[i][j]=t;
}
}
return tmp;
} mat MatQP(mat a,int n){
mat ans,tmp=a;
ans.r=ans.c=a.r;
memset(ans.m,,sizeof(ans.m));
for(int i=;i<=ans.r;i++){
ans.m[i][i]=;
}
while(n){
if(n&)ans=MatMul(ans,tmp);
n>>=;
tmp=MatMul(tmp,tmp);
}
return ans;
} int main(){
mat a;
a.r=;a.c=;
a.m[][]=;
a.m[][]=;
a.m[][]=;
mat t;
t.r=;
t.c=;
t.clear();
t.m[][]=;
t.m[][]=;
t.m[][]=;
t.m[][]=;
t.m[][]=;
int n;
while(scanf("%d%d",&n,&mod)!=EOF){
mat tmp=MatQP(t,n/);
tmp=MatMul(tmp,a);
printf("%lld\n",tmp.m[n%+][]);
}
return ;
}