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

· · 题解

题目大意

求：

\begin{cases} G_1 = 2 \\ G_2 = 3 \\ G_i = G_{i-1} \times G_{i-2} \ (i > 2) \end{cases}

的前 n 项积，其中 1\le n\le10^{18}。

解题思路

设前 n 项积为 P_i，注意到这个 P_i 的因子只由若干个 2 和 3 相乘组成，我们可以统计这个 2 的个数和 3 的个数然后用快速幂实现。在考场上我列出了两个表格来找这个规律。

第一个表格列的是 G_i 中因子 2 的个数和 3 的个数：

G_1 G_2 G_3 G_4 G_5 G_6 G_7
2 1 0 1 1 2 3 5
3 0 1 1 2 3 5 8

不难看出，无论是因子 2 的个数还是因子 3 的个数都组成了一个斐波那契数列。那么求前 n 项积的过程就转化为了求斐波那契数列的前 k 项和的过程。这个时候对斐波那契数列比较熟悉的小伙伴已经可以将公式写出来了，本人是个蒟蒻，在考场上没有想到这个结论，于是有了第二张表，即前 n 项积 P_i 所含因子 2 和因子 3 的个数：

P_1 P_2 P_3 P_4 P_5 P_6 P_7
2 1 1 2 3 5 8 13
3 0 1 2 4 7 12 20

这里我发现了在因子 2 的部分又出现了一个斐波那契数列，于是我大胆猜测：斐波那契数列的前 n 项和也跟斐波那契数列有关。在因子 2 的部分，其实是在斐波那契数列前加了一个 1 和一个 0 （忽略不计）之后得到的数列的前 k 项和（看第一张表），那么因子 3 部分得到的即为原斐波那契数列仅加了一个 0 后得到的前 k 项和。根据表可以写出：P_i 中因子 2 的指数为 F_i,而因子 3 的指数为 F_{i+1}-1，即：

P_i=2^{F_i}\times 3^{F_{i+1}-1}

赛后我对斐波那契数列的前 n 项和 S_i 进行了数学推导：

由于 F_i=F_{i+2}-F_{i+1}，那么

\begin{align*} S_n &= F_1 + F_2 + \cdots + F_n \\ &= (F_3 - F_2) + (F_4 - F_3) + (F_5 - F_4) + \cdots + (F_{n + 2} - F_{n + 1})\\ &=F_{n+2}-F_2\\ &=F_{n+2}-1 \end{align*}

突然发现：

1\le n\le 10^{18}

这个数据范围想要 O(n) 求指数 F_n 和 F_{n+1}-1 是不现实的，于是我想到了矩阵加速递推求斐波那契数列，这是一个非常模板的题，这里不再赘述。

但是指数会非常大，直接对指数取模怎么才能不对答案产生影响？根据费马小定理：

a^{p-1}\equiv 1 \pmod p

这里的 1 就是 a^0，998244353 是个质数，这里可以在求 F_n 的时候把答案对 998244353-1 取模以保证答案不变。

矩阵加速时间复杂度为 O(2^3\log n)（2^3 为矩阵乘法的常数），快速幂的复杂度 O(\log M)（M 为模数），总时间复杂度约为 O(\log n)，实测跑的飞快。

AC Code

防止作弊不放快读快写。

#define int long long
#define mod 998244353 
using namespace std;
struct matrix
{
    int num[3][3];
}e,a;//转移矩阵，原矩阵 
matrix operator*(const matrix &a,const matrix &b)
{
    matrix ans={};
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                ans.num[i][j]+=a.num[i][k]*b.num[k][j],ans.num[i][j]%=(mod-1);//注意这里取模是 mod-1 
    return ans;
}
matrix jzksm(matrix a,int b)//矩阵快速幂 
{
    matrix ans={};
    ans.num[1][1]=ans.num[2][2]=1;
    for(;b;b>>=1,a=a*a)
        if(b&1)
            ans=ans*a;
    return ans;
}
int ksm(int a,int b)//快速幂 
{
    int ans=1;
    for(;b;b>>=1,a*=a,a%=mod)
        if(b&1)
            ans*=a,ans%=mod;
    return ans;
}
signed main()
{
    int n=re();
    a.num[1][1]=a.num[1][2]=1;
    e.num[1][2]=e.num[2][1]=e.num[2][2]=1;
    matrix ans=a*jzksm(e,n-1);
    int anss=ksm(2,ans.num[1][1])*ksm(3,ans.num[1][2]-1)%mod;
    wr(anss);
    return 0;
}