P5136 sequence（矩阵快速幂）

数列的特征方程和特征根老师上课好像讲过然而我没听……以后老师上数学课要认真听了QAQ

设\(x=\frac{1+\sqrt{5}}{2},y=\frac{1-\sqrt{5}}{2}\)，那么\(x,y\)是\(t^2=t+1\)的两个解，也就是数列\(F_n=F_{n-1}+F_{n-2}\)的特征根

关于特征根是个什么神仙……可以这样理解，假设数列有\(F_n=c_1F_{n-1}+c_2F_{n-2}\)，则方程的特征根\(x_1,x_2\)为\(x^2=c_1x+c_2\)的两个解，那么原数列的通项公式为\(F_n=Ax_1^n+Bx_2^n\)

于是在这里我们令\(A=B=1\)，那么数列为\(F_n=x^n+y^n\)，代入得\(F_1=1,F_2=3\)，然后就可以用矩阵快速幂求出\(F_n\)，就能知道\(x^n=F_n-y^n\)

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

当\(n\)为偶数的时候，有\(0<y^n<1\)，则\(\lceil x^n\rceil=F_n\)

//minamoto

#include<bits/stdc++.h>

#define R register

#define ll long long

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(R int x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int P=998244353;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

struct Matrix{

	int a[2][2];

	Matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}

	inline int* operator [](const int &x){return a[x];}

	Matrix operator *(Matrix b){

		Matrix res;

		res[0][0]=add(mul(a[0][0],b[0][0]),mul(a[0][1],b[1][0]));

		res[0][1]=add(mul(a[0][0],b[0][1]),mul(a[0][1],b[1][1]));

		res[1][0]=add(mul(a[1][0],b[0][0]),mul(a[1][1],b[1][0]));

		res[1][1]=add(mul(a[1][0],b[0][1]),mul(a[1][1],b[1][1]));

		return res;

	}

}A,B;

ll n;

Matrix ksm(Matrix x,ll y){

	Matrix res;res[0][0]=res[1][1]=1;

	for(;y;y>>=1,x=x*x)if(y&1)res=res*x;

	return res;

}

int main(){

//	freopen("testdata.in","r",stdin);

	A[0][0]=A[0][1]=A[1][0]=1;

	int T=read();

	while(T--){

		n=read(),B[0][0]=3,B[0][1]=1;

		if(n<=2){print(n&1?2:3);continue;}

		B=B*ksm(A,n-2);

		print(B[0][0]+(n&1));

	}return Ot(),0;

}

巴特西

P5136 sequence（矩阵快速幂）

最新文章

热门文章