多项式乘法逆-Toy模板网

这篇具有很好参考价值的文章主要介绍了多项式乘法逆。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前置知识：NTT学习笔记（快速数论变换）

情景代入

洛谷P4238 【模板】多项式乘法逆

给定一个多项式 $f (x)$ ，求 $g (x)$ ，满足 $f(x)\times g(x)\equiv 1\pmod{x^n}$ 。系数对 $998244353$ 取模。

$1\leq n\leq 10^5,0\leq a_i\leq 10^9$

多项式乘法逆

上面这个问题，就是多项式乘法逆。

假设多项式 $f (x)$ 只有一项，那么显然 $g_0$ 为 $f_0$ 的逆元。如果 $n > 1$ ，则我们考虑递归求解。

假如我们已知 $h (x)$ ，满足 $f(x)\times h(x)\equiv 1\pmod{x^{\lceil\frac n2\rceil}}$ ，又因为 $f(x)\times g(x)\equiv 1\pmod{x^{\lceil\frac n2\rceil}}$ ，所以

$f(x)\times (g(x)-h(x))\equiv 0\pmod{x^{\lceil\frac n2\rceil}}$

由此可得 $g(x)-h(x)\equiv 0 \pmod{x^{\lceil\frac n2\rceil}}$ 。

两边同时平方。因为 $(g (x) - h (x))$ 的前 $\lceil\dfrac n2\rceil-1$ 项都是 $0$ ，而对于每一个 $k(0\leq k<n)$ ，能得到 $x^k$ 的两项 $x_i$ 和 $x_j(i+j=k)$ 中， $i$ 和 $j$ 至少有一个小于 $\lceil\dfrac n2\rceil$ ，也就是系数为 $0$ ，所以

$g(x)^2+h(x)^2-2g(x)\times h(x)\equiv 0\pmod{x^n}$

两边同时乘 $f (x)$ ,得 $f(x)g(x)^2+f(x)h(x)^2-2f(x)\cdot g(x)\cdot h(x)\equiv 0\pmod{x^n}$ 。又因为 $f(x)\cdot g(x)\equiv 1\pmod{x^n}$ ，所以

$g(x)\equiv 2h(x)-f(x)\cdot h(x)^2\pmod{x^n}$

用 $NTT$ 来做多项式乘法即可解决。

我们可以先求出 $g$ 值的前 $\lceil\dfrac n2\rceil$ 项，然后将 $h$ 值定为此时的 $g$ 值，接着就能求出 $g$ 值的前 $n$ 项。

这样递归，时间复杂度为 $O(n\log n)$ 。文章来源地址https://www.toymoban.com/news/detail-432761.html

code

#include<bits/stdc++.h>
using namespace std;
long long w,wn,f[500005],g[500005],a1[500005];
const long long G=3,mod=998244353;
long long mi(long long t,long long v){
	if(!v) return 1;
	long long re=mi(t,v/2);
	re=re*re%mod;
	if(v&1) re=re*t%mod;
	return re;
}
void ch(long long *a,int l){
	for(int i=1,j=l/2;i<l-1;i++){
		if(i<j) swap(a[i],a[j]);
		int k=l/2;
		while(j>=k){
			j-=k;k>>=1;
		}
		j+=k;
	}
}
void ntt(long long *a,int l,int fl){
	for(int i=2;i<=l;i<<=1){
		if(fl==1) wn=mi(G,(mod-1)/i);
		else wn=mi(G,mod-1-(mod-1)/i);
		for(int j=0;j<l;j+=i){
			w=1;
			for(int k=j;k<j+i/2;k++,w=w*wn%mod){
				long long t=a[k],u=w*a[k+i/2]%mod;
				a[k]=(t+u)%mod;
				a[k+i/2]=(t-u+mod)%mod;
			}
		}
	}
	if(fl==-1){
		long long ny=mi(l,mod-2);
		for(int i=0;i<l;i++) a[i]=a[i]*ny%mod;
	}
}
void solve(int l){
	if(l==1){
		g[0]=mi(f[0],mod-2);
		return;
	}
	solve((l+1)/2);
	int len=1;
	while(len<2*l) len<<=1;
	for(int i=0;i<l;i++) a1[i]=f[i];
	for(int i=l;i<len;i++) a1[i]=0;
	ch(a1,len);ch(g,len);
	ntt(a1,len,1);ntt(g,len,1);
	for(int i=0;i<len;i++){
		g[i]=(2-a1[i]*g[i]%mod+mod)%mod*g[i]%mod;
	}
	ch(g,len);ntt(g,len,-1);
	for(int i=l;i<len;i++) g[i]=0;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lld",&f[i]);
		f[i]%=mod;
	}
	solve(n);
	for(int i=0;i<n;i++){
		printf("%lld ",g[i]);
	}
	return 0;
}