专栏文章

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

DDavid_06
P12847题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mip30afk
此快照首次捕获于
2025/12/03 05:19
3 个月前
此快照最后确认于
2025/12/03 05:19
3 个月前
查看原文

题目大意

求： {G1=2G2=3Gi=Gi−1×Gi−2 (i>2)\begin{cases} G_1 = 2 \\ G_2 = 3 \\ G_i = G_{i-1} \times G_{i-2} \ (i > 2) \end{cases} 的前 nn 项积，其中 1≤n≤10181\le n\le10^{18}。

解题思路

设前 nn 项积为 PiP_i，注意到这个 PiP_i 的因子只由若干个 22 和 33 相乘组成，我们可以统计这个 22 的个数和 33 的个数然后用快速幂实现。在考场上我列出了两个表格来找这个规律。
第一个表格列的是 GiG_i 中因子 22 的个数和 33 的个数：
G1G_1G2G_2G3G_3G4G_4G5G_5G6G_6G7G_7
2211001111223355
3300111122335588
不难看出，无论是因子 22 的个数还是因子 33 的个数都组成了一个斐波那契数列。那么求前 nn 项积的过程就转化为了求斐波那契数列的前 kk 项和的过程。这个时候对斐波那契数列比较熟悉的小伙伴已经可以将公式写出来了，本人是个蒟蒻，在考场上没有想到这个结论，于是有了第二张表，即前 nn 项积 PiP_i 所含因子 22 和因子 33 的个数：
P1P_1P2P_2P3P_3P4P_4P5P_5P6P_6P7P_7
221111223355881313
33001122447712122020
这里我发现了在因子 22 的部分又出现了一个斐波那契数列，于是我大胆猜测：斐波那契数列的前 nn 项和也跟斐波那契数列有关。在因子 22 的部分，其实是在斐波那契数列前加了一个 11 和一个 00 （忽略不计）之后得到的数列的前 kk 项和（看第一张表），那么因子 33 部分得到的即为原斐波那契数列仅加了一个 00 后得到的前 kk 项和。根据表可以写出：PiP_i 中因子 22 的指数为 FiF_i,而因子 33 的指数为 Fi+1−1F_{i+1}-1，即：
Pi=2Fi×3Fi+1−1P_i=2^{F_i}\times 3^{F_{i+1}-1}
赛后我对斐波那契数列的前 nn 项和 SiS_i 进行了数学推导：
由于 Fi=Fi+2−Fi+1F_i=F_{i+2}-F_{i+1}，那么
Sn=F1+F2+⋯+Fn=(F3−F2)+(F4−F3)+(F5−F4)+⋯+(Fn+2−Fn+1)=Fn+2−F2=Fn+2−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≤n≤10181\le n\le 10^{18}
这个数据范围想要 O(n)O(n) 求指数 FnF_n 和 Fn+1−1F_{n+1}-1 是不现实的，于是我想到了矩阵加速递推求斐波那契数列，这是一个非常模板的题，这里不再赘述。
但是指数会非常大，直接对指数取模怎么才能不对答案产生影响？根据费马小定理：
ap−1≡1(modp)a^{p-1}\equiv 1 \pmod p
这里的 11 就是 a0a^0，998244353998244353 是个质数，这里可以在求 FnF_n 的时候把答案对 998244353−1998244353-1 取模以保证答案不变。
矩阵加速时间复杂度为 O(23log⁡n)O(2^3\log n)（232^3 为矩阵乘法的常数），快速幂的复杂度 O(log⁡M)O(\log M)（MM 为模数），总时间复杂度约为 O(log⁡n)O(\log n)，实测跑的飞快。

AC Code

防止作弊不放快读快写。
CPP
#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;
}

评论

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

正在加载评论...