HDU 4990 Reading comprehension(矩阵快速幂)题解

时间:2023-03-09 16:50:51
HDU 4990 Reading comprehension(矩阵快速幂)题解

思路:

如图找到推导公式,然后一通乱搞就好了

要开long long,否则红橙作伴

HDU 4990 Reading comprehension(矩阵快速幂)题解

代码:

#include<set>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
const int maxn = 3;
const int MOD = 1000000000+7;
const int INF = 0x3f3f3f3f;
using namespace std;
ll m;
struct Mat{
ll s[maxn][maxn];
void init(){
for(int i = 0;i < maxn;i++)
for(int j = 0;j < maxn;j++)
s[i][j] = 0;
}
}; Mat mul(Mat a,Mat b){
Mat t;
t.init();
for(int i = 0;i < maxn;i++){
for(int j = 0;j < maxn;j++){
for(int k = 0;k < maxn;k++){
t.s[i][j] = (t.s[i][j] + a.s[i][k]*b.s[k][j])%m;
}
}
}
return t;
}
Mat pow_mat(Mat p,int n){
Mat ret;
ret.init();
for(int i = 0;i < maxn;i++)
ret.s[i][i] = 1;
while(n){
if(n & 1) ret = mul(ret,p);
p = mul(p,p);
n >>= 1;
}
return ret;
}
int main(){
ll n;
while(scanf("%lld%lld",&n,&m) != EOF){
Mat A,B,T;
memset(T.s,0,sizeof(T.s));
memset(B.s,0,sizeof(B.s));
T.s[0][0] = T.s[1][0] = T.s[0][2] = T.s[2][2] = 1;
T.s[0][1] = 2;
if(n == 1) printf("%lld\n",1%m);
else if(n == 2) printf("%lld\n",2%m);
else{
B.s[0][0] = 2,B.s[1][0] = 1,B.s[2][0] = 1;
A = pow_mat(T,n - 2);
A = mul(A,B);
printf("%lld\n",A.s[0][0]);
}
}
return 0;
}