多项式求逆(倍增或分治FFT)

传送门

$$\begin{gathered} F(x)\ast H(x)\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\lceil \frac{n}{2}\rceil }) \\ 由题意得F(x)\ast G(x)\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\lceil \frac{n}{2}\rceil }) \\ 那么F(x)\ast [G(x)-H(x)]\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\lceil \frac{n}{2}\rceil }) \\ 就是G(x)-H(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\lceil \frac{n}{2}\rceil }) \\ 两边同时平方得到G(x{)}^2+H(x{)}^2-2G(x)H(x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n) \\ 模数变成x^n是有原因的,我们定义f(x)=G(x)-H(x),f(x{)}^2为f(x)\ast f(x) \\ 因为f_i^2=\sum _{j=0}^i{f}_j\ast f_{i-j} \\ 其中i和i-j不可能同时大于\frac{n}{2},所以一定有一项为0得证 \\ 我们再两边同时乘上F(x)得到,结合F(x)G(x)\equiv 1得到 \\ G(x)\equiv 2H(x)-F(x)H(x{)}^2(\mathrm{m}\mathrm{o}\mathrm{d}{x}^n) \end{gathered}$$

得到这个式子我们就可以倍增求解$G(x)$

就是先求模$x^1$下的$G(x)$

然后把这个$G(x)$作为$H(x)$,求模$x^2$下的$G(x)$

再求模$x^4$下的$G(x)$,问题得到解,乘法使用$NTT$求解

新版本

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6+10;
const int mod = 998244353, G = 3, Gi = (mod+1)/3;
int f[maxn],g[maxn],a[maxn],b[maxn],c[maxn],r[maxn],n;
int quick(int x,int n)
{
	int ans = 1;
	for( ; n ; n>>=1,x=x*x%mod )
		if( n&1 )	ans = ans*x%mod;
	return ans;
}
void NTT(int *a,int limit,int type)
{
	for(int i=0;i<limit;i++)
		if( i<r[i] )	swap( a[i],a[r[i]] );
	for(int mid=1;mid<limit;mid<<=1 )
	{
		int wn = quick( (type==1)?G:Gi,(mod-1)/(mid<<1) );
		for(int R=mid<<1,i=0;i<limit;i+=R )
		for(int w=1,k=0;k<mid;k++,w=w*wn%mod)
		{
			int x = a[i+k], y = a[i+mid+k]*w%mod;
			a[i+k] = (x+y)%mod, a[i+mid+k] = (x-y+mod)%mod;
		}
	}
	if( type==1 )	return;
	int inv = quick(limit,mod-2);
	for(int i=0;i<limit;i++)	a[i] = a[i]*inv%mod;
}
void solve(int bit,int *f,int *g)
{
	if( bit==1 ){ g[0] = quick(f[0],mod-2); return; }//递归边界 
	solve( (bit+1)>>1,f,g );//开始倍增,注意是向上取整(多了没关系,少了不行) 
	int limit = 1;
	while( limit<(bit<<1) )	limit<<=1;
	for(int i=0;i<limit;i++)
		r[i] = ( r[i>>1]>>1 ) | ( (i&1)?limit>>1:0 );
	for(int i=0;i<limit;i++)	a[i] = (i<bit?f[i]:0), b[i] = g[i];
	NTT(a,limit,1); NTT(b,limit,1);
	for(int i=0;i<limit;i++)	g[i] = (2-a[i]*b[i]%mod+mod)%mod*b[i]%mod;
	NTT(g,limit,-1);
	for(int i=bit;i<limit;i++)	g[i] = 0;
}
signed main()
{
	cin >> n;
	for(int i=0;i<n;i++)	cin >> f[i];
	solve(n,f,g);
	for(int i=0;i<n;i++)	printf("%lld ",g[i]);
} 

老版本:传送门

分治FFT

因为对于$k\in [1,n]$满足$\sum _{i+j==k}{F}_i{G}_j=0$

考虑求出了前$x-1$项的$G$如何求出$G_x$?

因为$\sum _{i=1}^x{F}_i{G}_{x-i+}+F_0{G}_x=0$

也就是$G_x=-\sum _{i=1}^x{F}_i{G}_{x-i}\ast \frac{1}{F_0}$

可以发现这个$G$数组其实就是可以分治$FFT$来求解

就是考虑求出了$[l,mid]$的$F$数值,累加贡献到$[mid+1,r]$上面去

就是拿$F_{l......mid}$去和$G_{1....r-l}$作卷积

其实就是多了个系数套模板了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e6+10;
const int mod = 998244353, G = 3, Gi = (mod+1)/G;
int ans[maxn],f[maxn],g[maxn],a[maxn],r[maxn],n;
int quick(int x,int n)
{
	int ans = 1;
	for( ; n ; n>>=1,x = x*x%mod )
		if( n&1 )	ans = ans*x%mod;
	return ans;
}
void init(int limit)
{
	for(int i=0;i<limit;i++)
		r[i] = ( r[i>>1]>>1 ) | ((i&1)?limit>>1:0 );
}
void NTT(int *a,int limit,int type)
{
	for(int i=0;i<limit;i++)
		if( i<r[i] )	swap( a[i],a[r[i]] );
	for(int mid=1;mid<limit;mid<<=1)//待合并区间长度 
	{
		int wn = quick( type==1?G:Gi,(mod-1)/(mid<<1) );
		for(int R=mid<<1,i=0;i<limit;i+=R )//i是待合并区间左端点 
		for(int k=0,w=1;k<mid;k++,w=w*wn%mod )
		{
			int x = a[i+k], y = a[i+k+mid]*w%mod;
			a[i+k] = ( x+y )%mod, a[i+k+mid] = ( x-y+mod )%mod;
		}
	}
}
void solve(int l,int r)
{
	if( l+1>=r )	return;
	int mid = l+r>>1;
	solve(l,mid);
	int len = r-l; init(len);
	for(int i=1;i<len;i++)	g[i] = a[i];
	for(int i=l;i<mid;i++)	f[i-l] = ans[i];
	for(int i=mid;i<r;i++)	f[i-l] = 0;
	NTT(f,len,1); NTT(g,len,1);
	for(int i=0;i<len;i++)	f[i] = f[i]*g[i]%mod;
	NTT(f,len,-1);
	int inv = quick(len,mod-2);
	int invv = quick( (-a[0]%mod+mod)%mod,mod-2 );
	for(int i=mid;i<r;i++)	ans[i] = ( ans[i]+f[i-l]*inv%mod*invv%mod )%mod;
	solve(mid,r);	
}
signed main()
{
	scanf("%lld",&n);
	for(int i=0;i<n;i++)	scanf("%lld",&a[i] );
	int limit = 1;
	while( limit<n )	limit<<=1;
	ans[0] = quick(a[0],mod-2);
	solve(0,limit);
	for(int i=0;i<n;i++)
		printf("%lld ",ans[i] );
}

最后

以上就是无奈电灯胆为你收集整理的多项式求逆(倍增或分治FFT)的全部内容，希望文章能够帮你解决多项式求逆(倍增或分治FFT)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。