98 lines
2.3 KiB
Markdown
98 lines
2.3 KiB
Markdown
## [$P1939$ 【模板】矩阵加速（数列）](https://www.luogu.com.cn/problem/P1939)
|
||
|
||
|
||
### 一、题目描述
|
||
|
||
|
||
|
||
### 二、解题思路
|
||
从题目上来看，知道需要递推求公式，但$n<=2e9$,我们知道简单递推肯定要挂掉。
|
||
|
||
所以想到需要一个$O(NlogN)$的算法,递推求式子，线性的还不行，联想到矩阵快速幂。
|
||
|
||
$$\large \begin{bmatrix}f_{x-3} & f_{x-2} & f_{x-1} \end{bmatrix} \times
|
||
\begin{bmatrix}
|
||
a&b &c \\
|
||
d&e &f \\
|
||
g&h &i
|
||
\end{bmatrix} = \begin{bmatrix}f_{x-2} & f_{x-1} & f_{x} \end{bmatrix}
|
||
$$
|
||
|
||
$\therefore$
|
||
$\large f_{x-3} \times a+f_{x-2}\times d + f_{x-1}\times g =f_{x-2}$
|
||
$\large f_{x-3} \times b+f_{x-2}\times e + f_{x-1}\times h =f_{x-1}$
|
||
$\large f_{x-3} \times c+f_{x-2}\times f + f_{x-1}\times i =f_{x}$
|
||
|
||
对比观察得到:
|
||
$a=0,d=1,g=0$
|
||
$b=0,e=0,h=1$
|
||
$c=1,f=0,i=1$
|
||
|
||
得到
|
||
$$m=\begin{bmatrix}
|
||
0& 0 & 1 \\
|
||
1& 0 & 0 \\
|
||
0& 1 & 1
|
||
\end{bmatrix}$$
|
||
|
||
而初始化矩阵$b=\begin{bmatrix} f_{1}& f_{2} & f_3 \end{bmatrix}=\begin{bmatrix} 1&1&1 \end{bmatrix}$
|
||
|
||
**递推式**：
|
||
$\large b=\begin{bmatrix}f_{x-2}& f_{x-1} & f_x \end{bmatrix}=
|
||
\begin{bmatrix}f_{1}& f_{2} & f_3 \end{bmatrix} \times
|
||
\begin{bmatrix}
|
||
0& 0 & 1 \\
|
||
1& 0 & 0 \\
|
||
0& 1 & 1
|
||
\end{bmatrix}^{n-3}
|
||
$
|
||
|
||
**答案**：
|
||
$\large b[0][2]$
|
||
|
||
$Code$
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
#define endl "\n"
|
||
const int MOD = 1e9 + 7;
|
||
const int N = 4;
|
||
int n;
|
||
|
||
// 矩阵乘法
|
||
void mul(int a[][N], int b[][N], int c[][N]) {
|
||
int t[N][N] = {0};
|
||
for (int i = 0; i < N; i++)
|
||
for (int j = 0; j < N; j++)
|
||
for (int k = 0; k < N; k++)
|
||
t[i][j] = (t[i][j] + (a[i][k] * b[k][j] % MOD)) % MOD;
|
||
memcpy(c, t, sizeof t);
|
||
}
|
||
|
||
void solve() {
|
||
int b[N][N] = {1, 1, 1}, m[N][N] = {0};
|
||
m[0][2] = m[1][0] = m[2][1] = m[2][2] = 1;
|
||
|
||
for (int i = n - 3; i; i >>= 1) {
|
||
if (i & 1) mul(b, m, b);
|
||
mul(m, m, m);
|
||
}
|
||
|
||
printf("%lld\n", b[0][2]);
|
||
}
|
||
|
||
signed main() {
|
||
int T;
|
||
cin >> T;
|
||
while (T--) {
|
||
cin >> n;
|
||
if (n <= 3) {
|
||
printf("1\n");
|
||
continue;
|
||
}
|
||
solve();
|
||
}
|
||
}
|
||
|
||
``` |