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

· · 题解

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

看到题解全是猜的，来发一个有推导过程过程的题解

分析

首先 G_i=G_{i-1} \times G_{i-2}

用我们高中常用的方法，两边同时取对数

ln(G_i)=ln(G_{i-1})+ln(G_{i-2})

现在就是普通的斐波那契数列，可以拆解为两个数列 第一个

F_i=ln(2)\times G_i

而 G_i 满足

\begin{cases} G_1=1\\ G_2=0\\ G_i=G_{i-1}+G_{i-2} \end{cases}

和 第二个

F'_i=ln(3)\times G'_i

而 G'_i 满足

\begin{cases} G'_1=0\\ G'_2=1\\ G'_i=G'_{i-1}+G'_{i-2} \end{cases}

最终答案就是

\exp(\sum_{i=1}^{n}G_i\times ln(2)) \times \exp(\sum_{i=1}^{n}G'_i\times ln(3))=2^{\sum_{i=1}^{n}G_i}\times 3^{\sum_{i=1}^{n}G'_i}

在对数情况下，原式前n项积就是前n项和 可以使用斐波那契数列求和公式

\sum_{i=1}^{n}G_i=G_{n+2}-G_2

分别对两个数列求和就行

而求斐波那契数这样的递推式子直接使用矩阵快速幂

\begin{bmatrix} G_{n+2}\\ G_{n+1} \end{bmatrix} = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^{n} \times \begin{bmatrix} G_2\\ G_1 \end{bmatrix}

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod = 998244353;
typedef long long ll;

ll fib(ll a, ll b, ll n) {
    if (n == 0) return a % mod;
    if (n == 1) return b % mod;

    struct Mat {
        ll m[2][2];
        Mat operator*(const Mat &o) const {
            Mat r = {};
            for (int i = 0; i < 2; ++i)
                for (int j = 0; j < 2; ++j)
                    for (int k = 0; k < 2; ++k)
                        r.m[i][j] = (r.m[i][j] + m[i][k] * o.m[k][j] % mod) % mod;
            return r;
        }
    };

    auto mat_pow = [&](Mat base, ll exp) {
        Mat res = {{{1, 0}, {0, 1}}}; 
        while (exp) {
            if (exp & 1) res = res * base;
            base = base * base;
            exp >>= 1;
        }
        return res;
    };

    Mat base = {{{1, 1}, {1, 0}}};
    Mat res = mat_pow(base, n - 1);

    return (res.m[0][0] * b % mod + res.m[0][1] * a % mod) % mod;
}
int fastpow(int a, int b){
    int res=1;
    while(b){
        if(b&1){
            res=(res*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    } 
    return res;
}
void solve(){
    int n;
    cin >> n;
    int a=1,b=0;
    mod--;
    int q=fib(a,b,n+1)-b;
    a=0,b=1;
    int p=fib(a,b,n+1)-b;
    mod++;
    //cout << p << " " << q << endl;
    int ans=fastpow(2,q);
    ans*=fastpow(3,p);
    ans%=mod;
    cout << ans << endl;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}

注意

不要忘了次数在取模时根据费马小定理 mod 的值应该为 mod-1