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
",ans);
}
return 0;
}
矩阵快速幂
1 #include<stdio.h>
2 #include<string.h>
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
",tmp.m[n%2+1][1]);
65 }
66 return 0;
67 }