自动搬运

查看原文

来自洛谷，原作者为

	Great_Influence **

搬运于2025-08-24 22:00:53，当前版本为作者最后更新于2018-05-07 20:19:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

要做这道题，先保证你会多项式求逆。

再发一下我参考的博客: Miskcoo's Space。

具体来说，设多项式 $A$ 为 $n$ 次多项式，考虑一种操作 $R$ ，使得

$$A_R(x) = x^n A(\frac{1}{x})$$

稍微想象一下，可以发现 $A_R[i] = A[n-i]$ ( $[i]$ 表示多项式的第 $i$ 次系数)。

这个操作可以 $O(n)$ 完成。

然后开始化式子。

$$F(x) = Q(x) * G(x) + R(x)$$ $$F(\frac{1}{x}) = Q(\frac{1}{x}) * G(\frac{1}{x}) + R(\frac{1}{x}) $$$$x^n F(\frac{1}{x}) = x^{n-m} Q(\frac{1}{x}) * x^m G(\frac{1}{x}) + x^{n-m+1} * x^{m-1} R(\frac{1}{x}) $$$$F_R(x) = Q_R(x) * G_R(x) + x^{n-m+1} * R_R(x)$$ $$F_R(x) \equiv Q_R(x) * G_R(x) + x^{n-m+1} * R_R(x)\pmod {x^{n-m+1}} $$$$F_R(x) \equiv Q_R(x) * G_R(x)\pmod {x^{n-m+1}}$$ $$Q_R(x) \equiv F_R(x) * G_R^{-1}(x)\pmod {x^{n-m+1}} $$

求一遍 $G_R$ 的逆，然后就可以利用多项式乘法求出 $Q$ 。然后

$$R(x) = F(x) - G(x) * Q(x)$$

直接计算即可。时间复杂度$O(n\log n)$。

代码:

#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Forward(i,a,b) for(i=(a);i>=(b);--i)
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
using namespace std;
template<typename T>inline void read(T &x){
    T s=0,f=1;char k=getchar();
    while(!isdigit(k)&&k^'-')k=getchar();
    if(!isdigit(k)){f=-1;k=getchar();}
    while(isdigit(k)){s=s*10+(k^48);k=getchar();}
    x=s*f;
}
void file(void){
    #ifndef ONLINE_JUDGE
    freopen("NTT.in","r",stdin);
    freopen("NTT.out","w",stdout);
    #endif
}
const int MAXN=1<<20;

typedef long long ll;

namespace polynomial
{
	static int mod=998244353,gen=3,g[21],rev[MAXN],Len;

	inline int ad(int a,int b){return (a+=b)>=mod?a-mod:a;}

	inline int power(int a,int b)
	{
		static int sum;
		for(sum=1;b;b>>=1,a=(ll)a*a%mod)if(b&1)
			sum=(ll)sum*a%mod;
		return sum;
	}

	inline void predone()
	{
		static int i,j;
		for(i=1,j=2;i<=19;++i,j<<=1)g[i]=power(gen,(mod-1)/j);
	}

	inline void calrev(int Len)
	{
		static int Logl;Logl=(int)floor(log(Len)/log(2)+0.3)-1;
		Rep(i,1,Len-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<Logl);
	}

	inline void NTT(int X[],int typ)
	{
		Rep(i,1,Len-1)if(i<rev[i])swap(X[i],X[rev[i]]);
		static int i,j,k,kk,w,t,wn,r;
		for(k=2,kk=1,r=1;k<=Len;k<<=1,kk<<=1,++r)
		{
			wn=g[r];
			for(i=0;i<Len;i+=k)for(j=0,w=1;j<kk;++j,w=(ll)w*wn%mod)
			{
				t=(ll)w*X[i+j+kk]%mod;
				X[i+j+kk]=ad(X[i+j],mod-t);
				X[i+j]=ad(X[i+j],t);
			}
		}
		if(typ==-1)
		{
			reverse(X+1,X+Len);
			static int invn;invn=power(Len,mod-2);
			Rep(i,0,Len-1)X[i]=(ll)X[i]*invn%mod;
		}
	}

	static int x[MAXN],y[MAXN];
	inline void mul(int a[],int b[])
	{
		memset(x,0,sizeof x);memset(y,0,sizeof y);
		Rep(i,0,(Len>>1)-1)x[i]=a[i],y[i]=b[i];
		NTT(x,1);NTT(y,1);
		Rep(i,0,Len-1)x[i]=(ll)x[i]*y[i]%mod;
		NTT(x,-1);
		Rep(i,0,Len-1)a[i]=x[i];
	}
	
	static int c[2][MAXN];
	
	inline void Inv(int a[],int n)
	{
		static int t;t=0;
		memset(c,0,sizeof c);
		c[0][0]=power(a[0],mod-2);
		Len=2;
		while(Len<=(n<<1))
		{
			Len<<=1;
			calrev(Len);t^=1;
			memset(c[t],0,sizeof c[t]);
			Rep(i,0,Len)c[t][i]=ad(c[t^1][i],c[t^1][i]);
			mul(c[t^1],c[t^1]);mul(c[t^1],a);
			Rep(i,0,Len)c[t][i]=ad(c[t][i],mod-c[t^1][i]);
		}
		Rep(i,0,Len-1)a[i]=c[t][i];
	}
}
using namespace polynomial;

int n,m,F[MAXN],G[MAXN],Q[MAXN],R[MAXN],Gr[MAXN];

int main(void){
    file();
	read(n);read(m);
	Rep(i,0,n)read(F[i]),Q[n-i]=F[i];
	Rep(i,0,m)read(G[i]),Gr[m-i]=G[i];
	Rep(i,n-m+2,m)Gr[i]=0;
	predone();
	Inv(Gr,n-m+1);
	mul(Q,Gr);
	reverse(Q,Q+n-m+1);
	Rep(i,n-m+1,n)Q[i]=0;
	Rep(i,0,n-m)printf("%d ",Q[i]);
	puts("");
	while(Len<=(n<<2))Len<<=1;
	calrev(Len);
	mul(Q,G);
	Rep(i,0,m-1)printf("%d ",ad(F[i],mod-Q[i]));
	puts("");
	return 0;
}