【Luogu4723】线性递推（常系数齐次线性递推）

题面

题解

板子题QwQ，注意多项式除法那里每个多项式的系数，调了一天。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAX 200000

#define MOD 998244353

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int fpow(int a,int b)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

int r[MAX],W[MAX];

void NTT(int *P,int opt,int N)

{

	int l=0;for(int i=1;i<N;i<<=1)++l;

	for(int i=0;i<N;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

	for(int i=0;i<N;++i)if(i<r[i])swap(P[i],P[r[i]]);

	for(int i=1;i<N;i<<=1)

	{

		int w=fpow(3,(MOD-1)/(i<<1));W[0]=1;

		for(int k=1;k<i;++k)W[k]=1ll*W[k-1]*w%MOD;

		for(int p=i<<1,j=0;j<N;j+=p)

			for(int k=0;k<i;++k)

			{

				int X=P[j+k],Y=1ll*W[k]*P[i+j+k]%MOD;

				P[j+k]=(X+Y)%MOD;P[i+j+k]=(X-Y+MOD)%MOD;

			}

	}

	if(opt==-1)

	{

		reverse(&P[1],&P[N]);

		for(int i=0,inv=fpow(N,MOD-2);i<N;++i)P[i]=1ll*P[i]*inv%MOD;

	}

}

int A[MAX],B[MAX];

void Inv(int *a,int *b,int len)

{

	if(len==1){b[0]=fpow(a[0],MOD-2);return;}

	Inv(a,b,len>>1);

	for(int i=0;i<len;++i)A[i]=a[i],B[i]=b[i];

	NTT(A,1,len<<1);NTT(B,1,len<<1);

	for(int i=0;i<len<<1;++i)A[i]=1ll*A[i]*B[i]%MOD*B[i]%MOD;

	NTT(A,-1,len<<1);

	for(int i=0;i<len;++i)b[i]=(b[i]+b[i])%MOD;

	for(int i=0;i<len;++i)b[i]=(b[i]+MOD-A[i])%MOD;

	for(int i=0;i<len<<1;++i)A[i]=B[i]=0;

}

int n,k,f[MAX],a[MAX];

int ans[MAX],s[MAX];

int Q[MAX],InvG[MAX],G[MAX],N;

int tmp[MAX];

void Mod(int *F,int *R)

{

	reverse(&F[0],&F[k+k-1]);

	for(int i=0;i<k;++i)tmp[i]=F[i];NTT(tmp,1,N);

	for(int i=0;i<N;++i)Q[i]=1ll*tmp[i]*InvG[i]%MOD;

	NTT(Q,-1,N);

	for(int i=k-1;i<N;++i)Q[i]=0;

	reverse(&F[0],&F[k+k-1]);reverse(&Q[0],&Q[k-1]);

	NTT(Q,1,N);

	for(int i=0;i<N;++i)Q[i]=1ll*G[i]*Q[i]%MOD;

	NTT(Q,-1,N);

	for(int i=0;i<k;++i)R[i]=(F[i]+MOD-Q[i])%MOD;

	for(int i=k;i<N;++i)R[i]=0;

	for(int i=0;i<N;++i)Q[i]=tmp[i]=0;

}

void Multi(int *a,int *b)

{

	NTT(a,1,N);NTT(b,1,N);

	for(int i=0;i<N;++i)a[i]=1ll*a[i]*b[i]%MOD;

	NTT(a,-1,N);NTT(b,-1,N);

	Mod(a,a);

}

void fpow(int b)

{

	s[1]=1;ans[0]=1;

	while(b)

	{

		if(b&1)Multi(ans,s);

		NTT(s,1,N);

		for(int i=0;i<N;++i)s[i]=1ll*s[i]*s[i]%MOD;

		NTT(s,-1,N);Mod(s,s);

		b>>=1;

	}

}

int main()

{

	n=read();k=read();

	for(int i=1;i<=k;++i)f[i]=(read()%MOD+MOD)%MOD;

	for(int i=0;i<k;++i)a[i]=(read()%MOD+MOD)%MOD;

	for(int i=1;i<=k;++i)G[k-i]=(MOD-f[i])%MOD;G[k]=1;

	reverse(&G[0],&G[k+1]);

	for(N=1;N<=k;N<<=1);N<<=1;Inv(G,InvG,N);

	for(int i=k+1;i<N;++i)InvG[i]=0;

	reverse(&G[0],&G[k+1]);

	NTT(G,1,N);NTT(InvG,1,N);

	fpow(n);int Ans=0;

	for(int i=0;i<k;++i)Ans=(Ans+1ll*a[i]*ans[i])%MOD;

	printf("%d\n",Ans);

	return 0;

}

巴特西

【Luogu4723】线性递推（常系数齐次线性递推）

【Luogu4723】线性递推（常系数齐次线性递推）

题面

题解

最新文章

热门文章