题解：P12847 [蓝桥杯 2025 国 A] 斐波那契数列
xhxxwcr
·
·
题解
题外话
截止 2025.6.16 上午 11:00，本人以 60ms 的成绩成功占领本题最优解榜一,欢迎挑战。
挑战成功的（~那可太有生活了~）私信我，我来继续改代码哈哈哈哈哈哈哈...（~已岔气~）
方法思路
数列 G 的每一项可以表示为 2 和 3 的幂次乘积（~这 TM 不显然吗？~），我们可以写作：2^{a_i} \times 3^{b_i}。
通过观察，数列 a 和 b 的递推关系类似于斐波那契数列：
a_1 = 1, a_2 = 0, a_i = a_{i-1} + a_{i-2} (i \ge 3 )
b_1 = 0, b_2 = 1, b_i = b_{i-1} + b_{i-2} ( i \geq 3 )
前 n 项的乘积 P(n) = G_1 \times G_2 \times \cdots \times G_n = 2^{S_A(n)} \times 3^{S_B(n)}，其中 S_A(n) = \sum_{i=1}^n a_i 和 S_B(n) = \sum_{i=1}^n b_i。
那 S_A(n) 和 S_B(n) 的值怎么算呢？
$S_B(n)$ 可以看做从 $i = 2$ 开始的标准等差数列求和。
又因为标准斐波那契数列的求和公式为:
$$(\sum_{i = 1}^n F_i) = F_{n + 2} - 1$$
所以 $S_A(n) = F_n$，$S_B(n) = F_{n + 1} - 1$。
不理解为什么的看[知乎q22319265](https://www.zhihu.com/question/22319265)。
所以可得：
$$P(n) = 2^{F_n} \times 3^{F_{n+1} - 1} \bmod 998244353$$。
**优化计算**：
~这数据一看就不能暴力啊，www~
- 使用矩阵快速幂计算斐波那契数列项 $F_n$ 和 $F_{n+1}$ 模 $998244352$（ $\varphi(998244353)$，因为指数部分需应用费马小定理）（~不会写矩阵快速幂的给我滚去看 [P1962](https://www.luogu.com.cn/problem/P1962)~）。
- 使用快速幂计算 $2^{F_n} \mod 998244353$ 和 $3^{F_{n+1}-1} \mod 998244353$，然后相乘并取模。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD1 = 998244353;
const int MOD2 = 998244352;
struct Matrix {
int a[3][3];
Matrix() {memset(a,0,sizeof a);}
Matrix operator*(const Matrix &b) const {
Matrix res;
for (int i = 1; i <= 2; ++i)
for (int j = 1; j <= 2; ++j)
for (int k = 1; k <= 2; ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % MOD2;
return res;
}
};
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
Matrix mpow(Matrix base, int p) {
Matrix res;
res.a[1][1] = res.a[2][2] = 1;
while (p) {
if (p & 1) {
res = res * base;
}
base = base * base;
p >>= 1;
}
return res;
}
int qpow(int a, int b, int p) {
a %= p;
int res = 1;
while (b > 0) {
if (b & 1) res = (res * a) % p;
a = (a * a) % p;
b >>= 1;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
/*cin.tie(0),*/cout.tie(0);
int n;
n = read();
if (n == 1) return cout << "2\n",0;
Matrix base;
base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;base.a[2][2] = 0;
Matrix t = mpow(base, n);
int Fn_1 = t.a[1][1],Fn = t.a[1][2];
int k1 = Fn % MOD2,k2 = (Fn_1 - 1 + MOD2) % MOD2;
int res1 = qpow(2, k1, MOD1),res2 = qpow(3, k2, MOD1);
int ans = (res1 * res2) % MOD1;
cout << ans << "\n";
return 0;
}
```