HDU 4990 Reading comprehension 矩阵快速幂

时间:2023-03-09 16:50:52
HDU 4990 Reading comprehension 矩阵快速幂

题意:

给出一个序列,

\(f_n=\left\{\begin{matrix}
2f_{n-1}+1, n \, mod \, 2=1\\
2f_{n-1}, n \, mod \, 2=0
\end{matrix}\right.\)

求\(f_n \, mod \, m\)的值。

分析:

我们可以两个两个的递推,这样就避免了奇偶讨论了。

$\begin{bmatrix}

0 & 2 & 1 \

0 & 4 & 2\

0 & 0 & 1

\end{bmatrix}

\begin{bmatrix}

f_1\

f_2\

1

\end{bmatrix}

\begin{bmatrix}

f_3\

f_4\

1

\end{bmatrix}$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long LL; LL n, MOD; LL mul_mod(LL a, LL b) { return a * b % MOD; } LL add_mod(LL& a, LL b) { a += b; if(a >= MOD) a -= MOD; } struct Matrix
{
LL a[3][3];
Matrix() { memset(a, 0, sizeof(a)); }
Matrix operator * (const Matrix& t) const {
Matrix ans;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
add_mod(ans.a[i][j], mul_mod(a[i][k], t.a[k][j]));
return ans;
}
}; Matrix pow_mod(Matrix a, LL n) {
Matrix ans;
for(int i = 0; i < 3; i++) ans.a[i][i] = 1;
while(n) {
if(n & 1) ans = ans * a;
a = a * a;
n >>= 1;
}
return ans;
} int main()
{
LL a0[3], a[3];
a0[0] = a0[2] = 1; a0[1] = 2;
Matrix M0;
M0.a[0][1] = 2; M0.a[1][1] = 4;
M0.a[0][2] = 1; M0.a[2][2] = 1;
M0.a[1][2] = 2; while(scanf("%lld%lld", &n, &MOD) == 2) {
Matrix M;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
M.a[i][j] = M0.a[i][j] % MOD;
for(int i = 0; i < 3; i++)
a[i] = a0[i] % MOD; M = pow_mod(M, (n - 1) / 2);
int x = ((n & 1) ^ 1);
LL ans = 0;
for(int i = 0; i < 3; i++)
add_mod(ans, mul_mod(M.a[x][i], a[i]));
printf("%lld\n", ans);
} return 0;
}