题解 P5136 【sequence】

Wolfycz · 2018-12-25 08:10:07 · 题解

我们打表可得，A_1=2,A_2=3,A_i=A_{i-1}+A_{i-2}-[i\%2==0]，然后记录三个信息矩阵快速幂一下，复杂度O(T*3^3\log n)，只有40pts(常数优秀的大佬应该可以有100pts)，然鹅吸个氧就可以过了（滑稽

不过考试时不能吸氧，于是我们考虑优化，但这个式子已经不好优化了，那么我们换个思路(其实是我不知道怎样优化这个式子)，令x=\dfrac{1+\sqrt{5}}{2},y=\dfrac{1-\sqrt{5}}{2}，不难发现x,y恰好为t^2=t+1的两个解。我们构造数列F_n=F_{n-1}+F_{n-2}，则x,y为F_n的两个特征根。我们令F_n=x^n+y^n，把n=1,2代入得到F_1=1,F_2=3，然后我们进行分类讨论：

• 当n为奇数，则有-1<y^n<0，此时\lceil x^n\rceil(A_n)=F_n+1
• 当n为偶数，则有0<y^n<1，此时\lceil x^n\rceil(A_n)=F_n

所以我们只要求出F_n，即可求出A_n，因为F_n=F_{n-1}+F_{n-2}，所以我们使用矩阵快速幂即可，复杂度O(T*2^3\log n)

/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
    int x=0,f=1;char ch=gc();
    for (;ch<'0'||ch>'9';ch=gc())   if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}
inline void print(int x){
    if (x<0)    putchar('-'),x=-x;
    if (x>9)    print(x/10);
    putchar(x%10+'0');
}
const int p=998244353;
struct Matrix{
    int v[2][2];
    Matrix(){memset(v,0,sizeof(v));}
    void clear(){memset(v,0,sizeof(v));}
    void init(){for (int i=0;i<2;i++)   v[i][i]=1;}
}A,B;
Matrix operator *(const Matrix &x,const Matrix &y){
    Matrix z;
    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++)
            for (int k=0;k<2;k++)
                z.v[i][k]=(z.v[i][k]+1ll*x.v[i][j]*y.v[j][k])%p;
    return z;
}
Matrix mlt(Matrix a,ll b){
    Matrix res; res.init();
    for (;b;b>>=1,a=a*a)    if (b&1)    res=res*a;
    return res;
}
int main(){
    A.v[0][0]=A.v[0][1]=A.v[1][0]=1;
    for (int T=read();T;T--){
        ll n; scanf("%lld",&n);
        B.v[0][0]=3,B.v[0][1]=1;
        if (n<=2){
            printf(n==1?"2\n":"3\n");
            continue;
        }
        B=B*mlt(A,n-2);
        printf("%d\n",B.v[0][0]+(int)(n&1));
    }
    return 0;
}