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

题外话

截止 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_A(n)

可以看做从

i = 3

开始的标准斐波那契数列求和再

+1

。

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。

所以可得：

P(n) = 2^{F_n} \times 3^{F_{n+1} - 1} \bmod 998244353

。

优化计算：
~这数据一看就不能暴力啊，www~

使用矩阵快速幂计算斐波那契数列项 $F_n$ 和 $F_{n+1}$ 模 $998244352$ （ $\varphi(998244353)$ ，因为指数部分需应用费马小定理）（~不会写矩阵快速幂的给我滚去看 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;
}

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

文章操作

题外话

方法思路

相关推荐

评论

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