矩阵快速幂模板
作者:
Qjwwww
,
2022-04-08 14:06:16
,
所有人可见
,
阅读 204
#include<bits/stdc++.h>
using namespace std;
struct martix{
long long m[5][5];
}A,B,C;
//用结构体代替二维数组,避免函数传递的麻烦事~
long long n,M;
martix Mul(martix m1,martix m2)
{
martix E;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
E.m[i][j] = 0;
}
}
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
for(int k=1;k<=3;k++)
{
E.m[i][j]+=m1.m[i][k]*m2.m[k][j];
}
E.m[i][j]%=M;
}
}
return E;
}
martix power(int k)
{
martix E,B2;
B2 = B;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
if(i==j) E.m[i][j] = 1;
else E.m[i][j] = 0;
}
}
//快速幂模板
//E相当于单位矩阵
while(k)
{
if(k%2==1) E = Mul(E,B2);
B2 = Mul(B2,B2);
k=k>>1;
}
return E;
}
int main()
{
memset(B.m,0,sizeof(B.m));
memset(C.m,0,sizeof(C.m));
B.m[1][1] = 1,B.m[1][2] = 1,B.m[1][3] = 1,B.m[2][1] = 0,B.m[2][2] = 1,B.m[2][3] = 1,B.m[3][1] = 0,B.m[3][2] = 1,B.m[3][3] = 0;
C.m[1][1] = 2,C.m[2][1] = 1,C.m[3][1] = 1;
cin>>n>>M;
if(n<=2) cout<<n%M;
else {
martix r = power(n-2);
A = Mul(r,C);
cout<<A.m[1][1];
}
return 0;
}