专栏文章

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

IInterRiver
P12847题解参与者 7已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@mip30cfb
此快照首次捕获于
2025/12/03 05:20
3 个月前
此快照最后确认于
2025/12/03 05:20
3 个月前
查看原文
在赛场上，注意到了一个事情：
p=998,244,353p = 998,244,353 时，令 c=37,748,736c = 37,748,736，有 ∏i=1cgi≡1(modp)\prod_{i = 1}^{c} g_i \equiv 1 \pmod p，且 gc+1=2, gc+2=3g_{c + 1} = 2, \, g_{c + 2} = 3。完美的循环！因此可以 O(c)O(c) 暴力求解。
以上，确实是我的赛时写法，但是这或许不是出题人的本意。
显然 gig_i 的因数只有 22 和 33，可以把两种因数分来开看。gig_i 中的因数的个数正是 gi−1g_{i - 1} 和 gi−2g_{i - 2} 中的因数的数量之和，这是一个类似于斐波那契数列的形式，可以用矩阵快速幂求得。为了求出数列的前 nn 项和，可以为矩阵加上第三维用来维护求和，这是很常见的手段。
用来做快速幂的矩阵
A=[010110101]A = \left[ \begin{array}{l} 0 & 1 & 0\\ 1 & 1 & 0\\ 1 & 0 & 1 \end{array} \right]
对向量
q=[abc]\boldsymbol{q} = \left[ \begin{array}{l} a \\ b \\ c \end{array} \right]
有
Aq=[ba+bc+a]A\boldsymbol{q} = \left[ \begin{array}{l} b \\ a + b \\ c + a \end{array} \right]
但是，这里有一个问题：我们求得的数字太大了，这个数字是在幂上的，能不能降幂呢？欧拉定理告诉我们：
若 gcd⁡(a,m)=1\gcd(a, m) = 1，则 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod m
因此在求 22 和 33 的幂次时，需要对 φ(p)=p−1\varphi(p) = p - 1 取模。
最后，22 的幂次的前两项为 [1,0][1, 0]，33 的幂次的前两项为 [0,1][0, 1]，则得到 sum_f 矩阵 MM 后，应当计算 M[1,0,0]TM[1, 0, 0]^{T} 的第三项作为答案中 22 的幂次，M[0,1,0]TM[0, 1, 0]^{T} 的第三项作为答案中 33 的幂次。
CPP
#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;
}
不过还有一个问题：循环节长度 cc 为什么是这么小的一个数，而非我一开始设想的 p2p^2 级别？期待其他大佬的解释。

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...