题解：P5136 sequence

· · 题解

本蒟蒻通过的第一道紫题，连夜肝出题解纪念。

思路

前置芝士：\ Lucas 数列

首先题目给出的数为 \phi，求 \phi 的 n 次幂并向上取整。题目背景也提到了数列，基于此不难想到斐波那契数列。

我们设 a = \dfrac{1+\sqrt{5}}{2} = \phi，b = \dfrac{1-\sqrt{5}}{2} = \psi。

Lucas 数列的递推式为 L_n = \begin{cases} 1 & n=1 \\ 2 & n=0 \\ L_{n-1}+L_{n-2} & n>1 \end{cases}，通项式为 L_{n} = a^{n} + b^{n}。

据此我们易知 a^{n} = L_n - b^{n}，注意到 \left| b \right| < 1，所以 \lim_{n \to \infty} b^n =0，因此 a^{n} \approx L_n，代入具体数字：

我们知道，当 n \equiv 1 \pmod{2} 时，b<0；否则 b>0。\ 也就是说当 n 为奇数时 a^n = L_n - b^n = L_n + |b^n| > L_n，否则 a^n = L_n - b^n < L_n

注意到题目要求的是 \lceil{a^n}\rceil，上文我们已经求出了 \left| b \right| < 1，所以在 a^n < L_n 的情况下对结果无影响；在 a^n > L_n 的情况下，需要加上 1。

综上所述，结论已经呼之欲出了，a^n=L_n+n \& 1。\ 现在我们只需要计算 Lucas 数列便可以了，聪明的你一定想到计算方法 ---- 矩阵快速幂！ 构造矩阵的方法就不介绍了。

代码

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

5pts

代码

5pts 越界优化版

代码

100pts

#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;
}