题解：P12847 [蓝桥杯 2025 国 A] 斐波那契数列

· · 题解

在赛场上，注意到了一个事情：

以上，确实是我的赛时写法，但是这或许不是出题人的本意。 显然 $g_i$ 的因数只有 $2$ 和 $3$，可以把两种因数分来开看。$g_i$ 中的因数的个数正是 $g_{i - 1}$ 和 $g_{i - 2}$ 中的因数的数量之和，这是一个类似于斐波那契数列的形式，可以用矩阵快速幂求得。为了求出数列的前 $n$ 项和，可以为矩阵加上第三维用来维护求和，这是很常见的手段。 用来做快速幂的矩阵 $$ A = \left[ \begin{array}{l} 0 & 1 & 0\\ 1 & 1 & 0\\ 1 & 0 & 1 \end{array} \right] $$ 对向量 $$ \boldsymbol{q} = \left[ \begin{array}{l} a \\ b \\ c \end{array} \right] $$ 有 $$ A\boldsymbol{q} = \left[ \begin{array}{l} b \\ a + b \\ c + a \end{array} \right] $$ 但是，这里有一个问题：我们求得的数字太大了，这个数字是在幂上的，能不能降幂呢？欧拉定理告诉我们： 若 $\gcd(a, m) = 1$，则 $a^{\varphi(m)} \equiv 1 \pmod m

因此在求 2 和 3 的幂次时，需要对 \varphi(p) = p - 1 取模。

最后，2 的幂次的前两项为 [1, 0]，3 的幂次的前两项为 [0, 1]，则得到 sum_f 矩阵 M 后，应当计算 M[1, 0, 0]^{T} 的第三项作为答案中 2 的幂次，M[0, 1, 0]^{T} 的第三项作为答案中 3 的幂次。

#include<bits/stdc++.h>
using namespace std;
typedef long long i64;

const i64 mod = 998244353;
const i64 mod1 = mod - 1;

struct Matrix {
    i64 v[3][3];
    void clear() {
        memset(v, 0, sizeof(v));
    }
};

Matrix operator * (const Matrix &A, const Matrix &B) {
    Matrix ret; ret.clear();
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                ret.v[i][j] = (ret.v[i][j] + A.v[i][k] * B.v[k][j]) % mod1;
    return ret;
}

Matrix sum_f(i64 n) {
    Matrix x, r;
    x.clear(); r.clear();
    x.v[0][1] = 1;
    x.v[1][0] = x.v[1][1] = 1;
    x.v[2][0] = x.v[2][2] = 1;
    r.v[0][0] = r.v[1][1] = r.v[2][2] = 1;
    while(n) {
        if(n & 1) r = r * x;
        x = x * x; n /= 2;
    }
    return r;
}

i64 qpow(i64 x, i64 p) {
    i64 r = 1;
    while(p) {
        if(p & 1) r = r * x % mod;
        x = x * x % mod; p /= 2;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    i64 n; cin >> n;
    Matrix m = sum_f(n);
    i64 p2 = m.v[2][0];
    i64 p3 = m.v[2][1];
    i64 ans = qpow(2, p2) * qpow(3, p3) % mod;
    cout << ans << endl;
    return 0;
}

不过还有一个问题：循环节长度 c 为什么是这么小的一个数，而非我一开始设想的 p^2 级别？期待其他大佬的解释。