多项式求逆与牛顿迭代法

“创造吧，向着未知深渊！”

牛顿-拉弗森迭代

~~虽然是由两个人一起发明的，但某人传着传着就不见了。~~

运用领域

给定一个已知多项式，现有一个未知多项式，满足：

$\nonumber g\Big(f(x)\Big)\equiv 0\pmod{ x^n}$

求模意义下的的系数。

这便是牛顿迭代法的最基本的用处，也是其通项。

此处的复合多项式表现为：

$g\Big(f(x)\Big)=(g\circ f)(x)=f_0+\sum_{k=1}^{\infty}f_kg^k(x)$

泰勒展开

关于泰勒展开

当我在搜索牛顿迭代的学习笔记的时候，几乎所有文章都将泰勒展开视为牛顿迭代的前置知识。

虽然我也不清楚泰勒展开究竟是数学实数领域下的前置知识，还是信息学多项式领域下的前置知识，所以我也学的很浅显（~~毕竟导数和微积分都没学过~~），所以稍微看看就好了。

泰勒展开，实则是将类似于三角函数（等），指数函数（等）难以直接计算的函数值用多项式的形式替换掉，通过迭代的方式，无限逼近使得二者的任意阶导数相等。

一般来讲，对于一个光滑函数，如果有：

$\nonumber f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(a)}{i!}(x-a)^n$

则该等式为在处的泰勒展开式。等式右部的部分称为处的泰勒级数。

什么是光滑函数？

光滑函数()是指在其定义域内无穷阶数连续可导的函数，即无穷阶可导的函数。

指数函数是光滑的，因为指数函数的导数是其本身。

在学习指数型生成函数的时候，我们已经在很多地方用到了泰勒展开，但那都是在处进行的泰勒展开。

特别地，在处的泰勒展开式与泰勒级数也被称为麦克劳林（）展开式和麦克劳林级数。

下表给出了一些常见的处泰勒级数（麦克劳林级数）：

$\begin{align} \frac{1}{1-x}&=\nonumber \sum_{n=0}^{\infty}x^n \\ (1-x)^{-m}&=\nonumber \sum_{n=0}^{\infty}\binom{n+m-1}{n}x^n \\ (1+x)^m&=\nonumber \sum_{n=0}^{\infty}\binom{m}{n}x^n \\ \ln(1-x)&=\nonumber -\sum_{n=0}^{\infty}\frac{x^n}{n} \\ \ln(1+x)&=\nonumber \sum_{n=1}^{\infty}\frac{(-1)^{n+1}x^n}{n} \\ \exp(x)&=\nonumber -\sum_{n=0}^{\infty}\frac{x^n}{n!} \end{align}$

请注意，泰勒展开并不一定对于定义域中的所有都成立，但在中，我们所研究的一般为形式幂级数，其展开式的系数于答案而言并没有什么影响，所以的值对我们也没什么影响。这一点在生成函数中也提到过。

多项式牛顿迭代

对于上述那个问题，我们来考虑求解。

所谓迭代，和我们上文提到的多项式分治有些类似，对于会被重复计算的元素，通过由已经得出的答案去推导未知答案的过程，层层递进，与的实现方式类似。

考虑一种倍增的思想。通过成倍增加来进行迭代。

那我们首先确立边界，当时，我们可以将的解手玩得到。其中表示的在处的系数。

然后考虑怎样进行迭代。

假设当前已经得到了在模意义下的函数记为，将在处进行泰勒展开得到：

$\sum_{i=0}^{\infty}\frac{g^{(i)}\big(f_0(x)\big)}{i!}\Big(f(x)-f_0(x)\Big)^i\equiv0\pmod{x^n} \nonumber$

可以得到：的最低非零项系数一定不小于，所以有：

$\forall 2\leq i:\Big(f(x)-f_0(x) \Big)^i\equiv 0\pmod {x^n}$

则有：

$\begin{align} \nonumber \sum_{i=0}^{\infty}\frac{g^{(i)}\big(f_0(x)\big)}{i!}\Big(f(x)-f_0(x)\Big)^i&\equiv g\big(f_0(x)\big)+g'\big(f_0(x)\big)\Big( f(x)-f_0(x) \Big)\equiv 0 \pmod{x^n} \\ \nonumber f(x)&\equiv f_0(x)-\frac{g\big(f_0(x)\big)}{g'\big(f_0(x)\big)}\pmod{x^n} \end{align}$

这就是从到的迭代，让我们的计算从优化到。

多项式求逆

对于一个次多项式，如果存在一个次多项式使得：

$F(x)\ast G(x)\equiv 1\pmod{x^n}$

则称为的逆。

关于这奇妙的模运算

网上基本上都是抄的一篇博客，屁都没讲，现在才体会到李煜东所说一份错误答案流传千古的感觉。找了好久才找到关于这个的意义。

此模运算属于多项式运算，即对于中，必须是一个多项式。按照此算式来讲，计算，得到的答案就是，容易发现，的卷积应当是一个次多项式。

所以，实际意义就是将中所有大于等于次项的系数全部视为，即舍弃大于等于次项的所有部分。

那对于多项式求逆而言，用通俗点的话来讲：

对于一个次多项式，如果存在一个多项式，两者乘积舍去大于次项的所有系数后，只有常数项为，都为，则称为的逆。

实现

既然只需要限制前次项，我们就可以通过牛顿迭代的思想来解决这个问题。

当时，，只有常数项，那么也有，则，就是一个乘法逆元的过程。

假设当前我们已经得到了在模意义下的逆，记为，则一定存在：

$\nonumber F(x)\ast G_0(x)\equiv 1\pmod{x^{\lceil \frac{n}{2}\rceil}}$

而又有：

$\nonumber F(x)\ast G(x)\equiv 1\pmod{x^{\lceil \frac{n}{2}\rceil}}$

这是必然存在的。

我们将两式相减并化简得到：

$\begin{align} F(x)\ast\Big(G(x)-G_0(x) \Big)&\equiv\nonumber (1-1)\pmod{x^{\lceil\frac{n}{2}\rceil}} \\ F(x)\ast\Big(G(x)-G_0(x) \Big)&\equiv\nonumber 0\pmod{x^{\lceil\frac{n}{2}\rceil}} \\ G(x)-G_0(x) &\equiv\nonumber 0\pmod{x^{\lceil\frac{n}{2}\rceil}} \end{align}$

在多项式的模运算中，存在性质：

$\begin{align} &a\equiv\nonumber b\pmod x^n \\ \Longleftrightarrow\nonumber &a^2\equiv b^2\pmod{x^{2n}} \end{align}$

这个性质仅在多项式意义下成立。那我们就对原式进行平方处理得到：

$\begin{align} G(x)-G_0(x) &\equiv\nonumber 0\pmod{x^{\lceil\frac{n}{2}\rceil}} \\ G^2(x)-2G(x)\ast G_0(x)+{G_0}^2(x)&\equiv\nonumber 0\pmod{x^{n}} \end{align}$

为什么要取上取整？

~~基于个人理解胡编乱造。~~

根据数学常识，有的情况存在，这是显然的。而对于我们的模而言，如果由于精度取舍变成了模的话，就会导致的缺失（强制为零），从而可能导致答案错误。

而又有，这样会使得原来的模可能晋升为的情况，从而使得不会强制为，但这并不会对我们的答案造成什么影响，因为我们每一次卷积运算只会运算项，而得到的非零项不过是一个不完整的完全卷积系数，而我们的判断并没有考虑过这个位置。

对原式同时乘上得到：

$\begin{align} F(x)\ast\Big(G^2(x)-2G(x)\ast G_0(x)+{G_0}^2(x)\Big)&\equiv\nonumber 0\pmod{x^{n}} \\ F(x)G(x)G(x)-2F(x)G(x)G_0(x)+F(x)G_0(x)G_0(x)&\equiv\nonumber 0\pmod{x^{n}} \end{align}$

因为有，所以得到：

$\begin{align} G(x)-2G_0(x)+F(x)\ast {G_0}^2(x)&\equiv\nonumber 0\pmod{x^n}\\ G(x)&\equiv\nonumber 2G_0(x)-F(x)\ast {G_0}^2(x)\pmod{x^n}\\ G(x)&\equiv\nonumber G_0(x)\Big( 2-F(x)G_0(x) \Big)\pmod{x^n} \end{align}$

这样的话，我们就可以通过和卷积得到，然后进行倍增，从在的时间呢扩展到真正的。

时间复杂度。据说使用牛顿迭代法是可以在一支下解决的，但不太清楚，~~能过就行~~。

AC Code

// ----- Eternally question-----
// Problem: P4238 【模板】多项式乘法逆
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4238
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-13 16:03:24
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=4e5+10;
const int P=998244353,G=3,invG=332748118;
int N;
ll f[MAXN],g[MAXN];
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%P;
		a=a*a%P;b>>=1;
	}
	return res;
}
int Rev[MAXN],Tot,Bit;
inline void Reverse(int n)
{
	while((1<<Bit)<=n) ++Bit;
	Tot=1<<Bit;
	for(int i=0;i<Tot;++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Bit-1));
}
inline void NTT(ll a[],int inv)
{
	for(int i=0;i<Tot;++i)
		if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
	for(int mid=1;mid<Tot;mid<<=1)
	{
		ll w1=qPow(inv==1?G:invG,(P-1)/(mid<<1));
		for(int i=0;i<Tot;i+=mid*2)
		{
			ll wk=1;
			for(int j=0;j<mid;++j,wk=wk*w1%P)
			{
				ll x=a[i+j],y=a[i+j+mid]*wk%P;
				a[i+j]=(x+y)%P,a[i+j+mid]=(x-y+P)%P;
			}
		}
	}
	if(inv==-1)
	{
		ll iv=qPow(Tot,P-2);
		for(int i=0;i<Tot;++i) a[i]=a[i]*iv%P;
	}
}
void solve(int n,ll f[],ll g[])
{
	if(n==1) return g[0]=qPow(f[0],P-2),void();
	solve((n+1)>>1,f,g);
	Reverse(n+N);
	static ll tmpf[MAXN],tmpg[MAXN];
	for(int i=0;i<Tot;++i)
	{
		tmpf[i]=f[i];
		tmpg[i]=(i<((n+1)>>1)?g[i]:0);
	}
	NTT(tmpf,1),NTT(tmpg,1);
	for(int i=0;i<Tot;++i) tmpf[i]=tmpg[i]*(((2-tmpf[i]*tmpg[i])%P+P)%P+P)%P;
	NTT(tmpf,-1);
	for(int i=0;i<Tot;++i) g[i]=tmpf[i];
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=0;i<N;++i) read(f[i]);
	solve(N,f,g);
	for(int i=0;i<N;++i) write(g[i],' ');
	return 0;
}
/*

*/

例题

分治 FFT

题目简介

题目名称：【模板】分治

题目来源：

评测链接：https://www.luogu.com.cn/problem/P4721

形式化题意：给定一个长度为的序列，并给定一个函数定义为：

求，对取模。

数据范围：

我们在之前的学习中用多项式分治解决了这个问题，现在，我们考虑是否可以用多项式求逆来解决这道题。首先设。

设不定项多项式，则有：

$\nonumber F(x)\ast G(x)=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}f(i)\times g(j)x^{i+j}$

我们令，换元得到：

$\nonumber F(x)\ast G(x)=\sum_{k=0}^{\infty}\sum_{j=0}^{k}f(k-j)\times g(j)x^k$

我们根据的大小进行分类讨论：

$F(x)\ast G(x)= \begin{cases} f(0)\times g(0)x^0=0&,k=0 \\ \sum\limits_{j=0}^{k}f(k-j)\times g(j)x^k=f(k)x^k&,k>0 \end{cases} \nonumber$

所以，我们可以得知：

$F(x)\ast G(x)=\sum_{i=1}^{\infty}f(i)x^i$

从而得到一个等式，并对其进行化简：

$\begin{align} F(x)\ast G(x)+f(0)&=\nonumber F(x) \\ F(x)\ast\big(G(x)-1\big)&=\nonumber -f(0) \\ F(x)&=\nonumber \frac{f(0)}{1-G(x)} \end{align}$

因为有，并设不定项多项式，可以得到的表达式，然后代入原式得到：

$\begin{align} \nonumber F(x)&=\frac{1}{H(x)} \\ F(x)\ast H(x)&\equiv\nonumber 1\pmod{x^{2n}} \end{align}$

多项式求逆即可。

AC Code

// ----- Eternally question-----
// Problem: P4721 【模板】分治 FFT
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4721
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-13 16:41:41
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=4e5+10;
const int P=998244353,G=3,invG=332748118;
int N;
ll f[MAXN],g[MAXN];
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%P;
		a=a*a%P;b>>=1;
	}
	return res;
}
int Rev[MAXN],Tot,Bit;
inline void reverse(int n)
{
	while((1<<Bit)<=n) ++Bit;
	Tot=1<<Bit;
	for(int i=0;i<Tot;++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Bit-1));
}
inline void NTT(ll a[],int inv)
{
	for(int i=0;i<Tot;++i)
		if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
	for(int mid=1;mid<Tot;mid<<=1)
	{
		ll w1=qPow(inv==1?G:invG,(P-1)/(mid<<1));
		for(int i=0;i<Tot;i+=mid*2)
		{
			ll wk=1;
			for(int j=0;j<mid;++j,wk=wk*w1%P)
			{
				ll x=a[i+j],y=a[i+j+mid]*wk%P;
				a[i+j]=(x+y)%P,a[i+j+mid]=(x-y+P)%P;
			}
		}
	}
	if(inv==-1)
	{
		ll iv=qPow(Tot,P-2);
		for(int i=0;i<Tot;++i) a[i]=a[i]*iv%P;
	}
}
void inverse(int n,ll f[],ll g[])
{
	if(n==1) return g[0]=qPow(f[0],P-2),void();
	inverse((n+1)>>1,f,g);
	reverse(n+N);
	static ll ftp[MAXN],gtp[MAXN];
	for(int i=0;i<Tot;++i) ftp[i]=f[i],gtp[i]=(i<((n+1)>>1))?g[i]:0;
	NTT(ftp,1),NTT(gtp,1);
	for(int i=0;i<Tot;++i) ftp[i]=gtp[i]*((2-ftp[i]*gtp[i]%P+P)%P+P)%P;
	NTT(ftp,-1);
	for(int i=0;i<Tot;++i) g[i]=ftp[i];
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N),g[0]=1;
	for(int i=1;i<N;++i) read(g[i]),g[i]=(P-g[i])%P;
	inverse(N,g,f);
	for(int i=0;i<N;++i) write(f[i],' ');
	return 0;
}
/*

*/

任意模数多项式求逆

题目简介

题目名称：任意模数多项式求逆
题目来源：

评测链接：https://www.luogu.com.cn/problem/P4239

形式化题意：给定一个次多项式，求一个多项式使得，对取模。

数据范围：

时空限制：

如果用做的话，并不是我们所能够使用的质数，所以我们需要的是三模数，用进行两两合并。

但注意在多项式求逆中我们需要的是卷积，所以在合并与时进行一些变式。

合并时会出现级别的模数，其计算会超标，所以可以选择龟速乘或者 __int128_t 来进行转化，但一个会使得时间复杂度多一支，一个会多一堆大常数，所以要进行优化。

最后的时间复杂度为。

三模数NTT

// ----- Eternally question-----
// Problem: P4239 任意模数多项式乘法逆
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4239
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-01-15 09:42:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=4e5+10;
const int Mod=1e9+7,G=3;
const ll P[]={0,469762049,998244353,1004535809};
int N;
ll f[MAXN],g[MAXN];
inline ll qPow(ll a,ll b,ll p)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p;b>>=1;
	}
	return res;
}
int Rev[MAXN],Bit,Tot;
inline void reverse(int n)
{
	Bit=0;
	while((1<<Bit)<=n) ++Bit;
	Tot=1<<Bit;
	for(int i=0;i<Tot;++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Bit-1));
}
inline void NTT(ll a[],int n,ll p,int inv)
{
	for(int i=0;i<n;++i)
		if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
	ll invG=qPow(G,p-2,p);
	for(int mid=1;mid<n;mid<<=1)
	{
		ll w1=qPow(inv==1?G:invG,(p-1)/(mid<<1),p);
		for(int i=0;i<n;i+=mid*2)
		{
			ll wk=1;
			for(int j=0;j<mid;++j,wk=wk*w1%p)
			{
				ll x=a[i+j],y=a[i+j+mid]*wk%p;
				a[i+j]=(x+y)%p,a[i+j+mid]=(x-y+p)%p;
			}
		}
	}
	if(inv==-1)
	{
		ll iv=qPow(n,p-2,p);
		for(int i=0;i<n;++i) a[i]=a[i]*iv%p;
	}
}
ll a[MAXN],b[MAXN];
inline void Mul(ll f[],ll g[],int n,ll p,ll ans[])
{
	// reverse(n);
	for(int i=0;i<n;++i) a[i]=f[i],b[i]=g[i];
	for(int i=n;i<Tot;++i) a[i]=b[i]=0;
	NTT(a,Tot,p,1),NTT(b,Tot,p,1);
	for(int i=0;i<Tot;++i) ans[i]=a[i]*b[i]%p;
	NTT(ans,Tot,p,-1);
	for(int i=n;i<Tot;++i) ans[i]=0;
}
const ll Ps=P[1]*P[2];
const ll iv1=qPow(P[2]%P[1],P[1]-2,P[1]),iv2=qPow(P[1]%P[2],P[2]-2,P[2]),iv3=qPow(Ps%P[3],P[3]-2,P[3]);
inline ll crt(ll a,ll b,ll c)
{
	using u128=__uint128_t;
	u128 x= (u128)P[2]*a*iv1+(u128)P[1]*b*iv2;
	ll _x=x%Ps;
	// ll _x=(P[2]*a%Ps*iv1%Ps+P[1]*b%Ps*iv2%Ps)%Ps;
	ll s=(c-_x%P[3]+P[3])*iv3%P[3];
	return (s%Mod*(Ps%Mod)%Mod+_x%Mod)%Mod;
}
inline void MTT(ll f[],ll g[],int n,ll res[])
{
	static ll ans[4][MAXN];
	for(int k=1;k<=3;++k) Mul(f,g,n,P[k],ans[k]);
	for(int i=1;i<n;++i)
	{
		ll ct=crt(ans[1][i],ans[2][i],ans[3][i]);
		for(int k=1;k<=3;++k) ans[k][i]=(Mod-ct)%Mod;
	}
	*ans[1]=*ans[2]=*ans[3]=1;
	for(int k=1;k<=3;++k) Mul(ans[k],g,n,P[k],ans[k]);
	for(int i=0;i<n;++i) res[i]=crt(ans[1][i],ans[2][i],ans[3][i]);
}
void inverse(int n,ll f[],ll g[])
{
	if(n==1) return *g=qPow(*f,Mod-2,Mod),void();
	inverse((n+1)>>1,f,g);
	reverse(n<<1);
	MTT(f,g,n,g);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=0;i<N;++i) read(f[i]),f[i]%=Mod;
	inverse(N,f,g);
	for(int i=0;i<N;++i) write(g[i],' ');
	return 0;
}
/*

*/

那如果使用拆系数写的话，就没有太多的繁琐步骤，但要注意精度和初始化问题。

拆系数FFT

// ----- Eternally question-----
// Problem: P4239 任意模数多项式乘法逆
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4239
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-01-15 11:27:22
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef long double ld;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=4e5+10;
const int Mod=1e9+7,Base=1<<15;
const ld pi=std::acos(-1);
int N;
ll f[MAXN],g[MAXN];
inline ll qPow(ll a,ll b,ll p)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p;b>>=1;
	}
	return res;
}
struct Complex
{
	ld x,y;
	Complex operator+(const Complex &a) const
	{ return Complex{x+a.x,y+a.y}; }
	Complex operator-(const Complex &a) const
	{ return Complex{x-a.x,y-a.y}; }
	Complex operator*(const Complex &a) const
	{ return Complex{x*a.x-y*a.y,x*a.y+y*a.x}; }
};
int Rev[MAXN],Tot,Bit;
inline void reverse(int n)
{
	Bit=0;
	while((1<<Bit)<=n) ++Bit;
	Tot=1<<Bit;
	for(int i=0;i<Tot;++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Bit-1));
}
inline void FFT(Complex a[],int n,int inv)
{
	for(int i=0;i<n;++i)
		if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
	for(int mid=1;mid<n;mid<<=1)
	{
		auto w1=Complex({std::cos(pi/mid),inv*std::sin(pi/mid)});
		for(int i=0;i<n;i+=mid*2)
		{
			auto wk=Complex({1,0});
			for(int j=0;j<mid;++j,wk=wk*w1)
			{
				auto x=a[i+j],y=a[i+j+mid]*wk;
				a[i+j]=x+y,a[i+j+mid]=x-y;
			}
		}
	}
	if(inv==-1) for(int i=0;i<n;++i) a[i].x/=1.0*n;
}
Complex a1[MAXN],b1[MAXN],a2[MAXN],b2[MAXN];
inline void MTT(ll a[],ll b[],int n,ll s[])
{
	reverse(n);
	for(int i=0;i<(n<<1);++i) a1[i]=a2[i]=b1[i]=b2[i]=Complex({0,0});
	for(int i=0;i<n;++i)
	{
		a[i]%=Mod,b[i]%=Mod;
		a1[i]=Complex({a[i]/Base*1.0,0});
		a2[i]=Complex({a[i]%Base*1.0,0});
		b1[i]=Complex({b[i]/Base*1.0,0});
		b2[i]=Complex({b[i]%Base*1.0,0});
	}
	FFT(a1,Tot,1),FFT(a2,Tot,1),FFT(b1,Tot,1),FFT(b2,Tot,1);
	for(int i=0;i<Tot;++i)
	{
		Complex tmp=a1[i]*b1[i];
		b1[i]=b1[i]*a2[i],a2[i]=a2[i]*b2[i],b2[i]=b2[i]*a1[i];
		a1[i]=tmp;b1[i]=b1[i]+b2[i];
	}
	FFT(a1,Tot,-1),FFT(a2,Tot,-1),FFT(b1,Tot,-1);
	for(int i=0;i<n;++i)
	{
		s[i]=0;
		s[i]=(s[i]+1ll*(ll)(a1[i].x+0.5)%Mod*Base%Mod*Base%Mod)%Mod;
		s[i]=(s[i]+1ll*(ll)(b1[i].x+0.5)%Mod*Base%Mod)%Mod;
		s[i]=(s[i]+1ll*(ll)(a2[i].x+0.5)%Mod)%Mod;
		s[i]=(s[i]+Mod)%Mod;
	}
}
void inverse(int n,ll f[],ll g[])
{
	if(n==1) return g[0]=qPow(f[0],Mod-2,Mod),void();
	inverse((n+1)>>1,f,g);
	// reverse(n<<1);
	static ll tf[MAXN],tg[MAXN];
	MTT(f,g,n,tf);MTT(tf,g,n,tg);
	for(int i=0;i<n;++i) g[i]=(g[i]+g[i])%Mod;
	for(int i=0;i<n;++i) g[i]=(g[i]-tg[i]+Mod)%Mod;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=0;i<N;++i) read(f[i]);
	reverse(N);
	inverse(Tot,f,g);
	for(int i=0;i<N;++i) write(g[i],' ');
	return 0;
}
/*

*/

~~每次MTT我们都来比较一下。~~

时空比较	三模数	拆系数
时间	不可过
空间
下

~~就不说啥了。~~

牛顿-拉弗森 迭代