专栏文章

题解：P5136 sequence

lliuhaoyan0323
P5136题解参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miqc96kn
此快照首次捕获于
2025/12/04 02:26
3 个月前
此快照最后确认于
2025/12/04 02:26
3 个月前
查看原文
本蒟蒻通过的第一道紫题，连夜肝出题解纪念。

思路

前置芝士：
Lucas 数列
首先题目给出的数为 ϕ\phi，求 ϕ\phi 的 nn 次幂并向上取整。题目背景也提到了数列，基于此不难想到斐波那契数列。
我们设 a=1+52=ϕa = \dfrac{1+\sqrt{5}}{2} = \phi，b=1−52=ψb = \dfrac{1-\sqrt{5}}{2} = \psi。
Lucas 数列的递推式为 Ln={1n=12n=0Ln−1+Ln−2n>1L_n = \begin{cases} 1 & n=1 \\ 2 & n=0 \\ L_{n-1}+L_{n-2} & n>1 \end{cases}，通项式为 Ln=an+bnL_{n} = a^{n} + b^{n}。
据此我们易知 an=Ln−bna^{n} = L_n - b^{n}，注意到 ∣b∣<1\left| b \right| < 1，所以 lim⁡n→∞bn=0\lim_{n \to \infty} b^n =0，因此 an≈Lna^{n} \approx L_n，代入具体数字：
  • n=1n=1，bn≈−0.618b^n \approx -0.618
  • n=2n=2，bn≈0.381b^n \approx 0.381
  • ……
我们知道，当 n≡1(mod2)n \equiv 1 \pmod{2} 时，b<0b<0；否则 b>0b>0。
也就是说当 nn 为奇数时 an=Ln−bn=Ln+∣bn∣>Lna^n = L_n - b^n = L_n + |b^n| > L_n，否则 an=Ln−bn<Lna^n = L_n - b^n < L_n
注意到题目要求的是 ⌈an⌉\lceil{a^n}\rceil，上文我们已经求出了 ∣b∣<1\left| b \right| < 1，所以在 an<Lna^n < L_n 的情况下对结果无影响；在 an>Lna^n > L_n 的情况下，需要加上 11。
综上所述，结论已经呼之欲出了，an=Ln+n&1a^n=L_n+n \& 1。
现在我们只需要计算 Lucas 数列便可以了，聪明的你一定想到计算方法 ---- 矩阵快速幂！ 构造矩阵的方法就不介绍了。

代码

矩阵快速幂的代码模板采用的是这个。

5pts5pts

代码

5pts5pts 越界优化版

代码

100pts100pts

CPP
#include<bits/stdc++.h>
#define int long long
#define N 3
#define MOD 998244353
using namespace std;
int base[N][N],tmp[N][N],n;
inline void Init();
inline void mult(int x[N][N],int y[N][N]);
inline int fpow(int b);
inline void read(int &num);
signed main(){
    int T;
    read(T);
    while(T--){
		Init();
    	read(n);
    	int res=fpow(n-1);
    	if(n&1)++res;
    	printf("%lld\n",res%MOD);
	}
}
inline void Init(){
    base[1][1]=0;
    base[1][2]=1;
    base[2][1]=1;
    base[2][2]=1;
}
inline void mult(int x[N][N],int y[N][N]){
    int tmp[N][N];
    for(int i=1;i<N;++i){
    	for(int j=1;j<N;++j){
            tmp[i][j]=0;
            for(int k=1;k<N;++k){
            	tmp[i][j]=(tmp[i][j]+x[i][k]*y[k][j])%MOD;
			}  
        }
	} 
    memcpy(x,tmp,sizeof(tmp));
}
inline int fpow(int b){
    int ans[N][N];
    for(int i=1;i<N;++i){
        for(int j=1;j<N;++j){
        	ans[i][j]=1;
		}
    }
    ans[1][1]=1;
    ans[1][2]=3;
    while(b){
        if(b&1)mult(ans,base);
        mult(base,base);
        b/=2;
    }
    return ans[1][1];
}
inline void read(int &num){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	num=x*f;
}

评论

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

正在加载评论...