/*
矩阵快速幂：
第n个人如果是m，有f(n-1)种合法结果
第n个人如果是f,对于第n-1和n-2个人有四种ff,fm,mf,mm其中合法的只有fm和mm
对于ffm第n-3个人只能是m那么有f(n-4)种
对于fmm那么对于第n-3个人没有限制有f(n-3)种
顾f(n)=f(n-1)+f(n-3)+f(n-4);
求出前四个结果分别是 a[1]=2;a[2]=4;a[3]=6;a[4]=9;
A=|a[4],a[3],a[2],a[1]|
可以构造矩阵
|1 1 0 0 |
B= |0 0 1 0 |
|1 0 0 1 |
|1 0 0 0 |
|1 1 0 0 |^n
|0 0 1 0 |
|a[4],a[3],a[2],a[1]|* |1 0 0 1 | = |a[5],a[4],a[3],a[2]|
|1 0 0 0 |
A*B^n=C;
直接套模板即可。
*/
#include<stdio.h>
#include<string.h>
#define N 11
int a[N];
struct matrix{
__int64 mat[5][5];
};
matrix matmul(matrix b,matrix c,int mm) {
int i,j,k;
matrix d;
memset(d.mat,0,sizeof(d.mat));
for(i=0;i<4;i++)
for(j=0;j<4;j++)
for(k=0;k<4;k++) {
d.mat[i][j]+=b.mat[i][k]*c.mat[k][j];
d.mat[i][j]%=mm;
}
return d;
}
matrix matpow(matrix f,matrix ff,int k,int m) {
while(k) {
if(k&1)
ff=matmul(ff,f,m);
f=matmul(f,f,m);
k/=2;
}
return ff;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF) {
a[1]=2;a[2]=4;a[3]=6;a[4]=9;
if(n<=4) {
printf("%d
",a[n]%m);
continue;
}
matrix aa,bb,cc;
memset(aa.mat,0,sizeof(aa.mat));
memset(bb.mat,0,sizeof(bb.mat));
aa.mat[0][0]=1;//构建矩阵
aa.mat[2][0]=1;
aa.mat[3][0]=1;
aa.mat[0][1]=1;
aa.mat[1][2]=1;
aa.mat[2][3]=1;
bb.mat[0][0]=a[4];
bb.mat[0][1]=a[3];
bb.mat[0][2]=a[2];
bb.mat[0][3]=a[1];
cc=matpow(aa,bb,n-4,m);
printf("%d
",cc.mat[0][0]);
}
return 0;}