多项式求逆
\[\begin{aligned} &F(x) * G(x) \equiv 1 \pmod{x^n} \\ &F(x) * G(x) \equiv 1 \pmod{x^{\lceil \frac{n}{2}\rceil}} \\ &我们设F(x)*H(x)\equiv 1 \pmod{x^{\lceil \frac{n}{2}\rceil}}\\ &F(x)*(G(x)-H(x)) \equiv 0 \pmod{x^{\lceil \frac{n}{2}\rceil}}\\ &(G(x)-H(x))\equiv 0 \pmod{x^{\lceil \frac{n}{2}\rceil}}\\ &(G(x)-H(x))^2\equiv 0 \pmod{x^n}\\ &G^2(x)+H^2(x)-2G(x)H(x)\equiv 0 \pmod{x^n}\\ &F(x)G^2(x)+F(x)H^2(x)-2F(x)G(x)H(x)\equiv 0 \pmod{x^n}\\ &G(x)+F(x)H^2(x)-2H(x)\equiv 0 \pmod{x^n}\\ & G(x)\equiv 2H(x)-F(x)H^2(x)\pmod{x^n}\\ &当n=1时，F(x)=[x^0]F(x)x,G(x)=([x^0]F(x)x)^{-1} \end{aligned} \]很多题解都采用了上面的证法，然而我初次看时有很多不理解的地方。其中最令我感到迷惑的是为什么用向上取整而不能用向下取整。现在给出解释:
\[\begin{aligned} 1. &a \equiv 1 \pmod {x^n} \Rightarrow a\equiv 1 \pmod {x^{\lceil \frac{n}{2}\rceil}}\\ 证明： &a \equiv 1 \pmod {x^n}\\ &x^n \mid a-1\\ &{x^{\lceil \frac{n}{2}\rceil}}{x^{\lfloor \frac{n}{2} \rfloor}} \mid a-1\\ &{x^{\lceil \frac{n}{2}\rceil}}\mid a-1\\ &a \equiv 1 \pmod {x^{\lceil \frac{n}{2}\rceil}}\\ &注意到，向下取整同样满足这个性质，然而这并不重要(主不在乎\\ 2.&a\equiv 0 \pmod {x^{\lceil \frac{n}{2}\rceil}} \rightarrow a^2\equiv 0 \pmod{x^n}\\ 证明： &a^2 \equiv 0 \pmod {x^{2 {\lceil \frac{n}{2}\rceil}}}\\ & x^{{\lceil \frac{n}{2}\rceil}} \mid a^2\\ & x^n\mid x^{2 {\lceil \frac{n}{2}\rceil}} \\ &a^2 \equiv 0 \pmod {x^n}\\ &注意到，向下取整并不满足这个性质，因此只能采取向上取整的方式\\ \end{aligned} \]有了这样的性质，最上面的证明自然就具有了正确性。
然而似乎并没有什么卵用，因为求逆是自底而上倍增实现的，根本用不着什么向下取整。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5e4;
const int P=998244353,g=3,gi=332748118;
int lim=1,r[maxn],c[maxn],w[maxn];
void joke()
{
//joke说加个空函数跑的能快点
}
int fsp(int a,int b=P-2)
{
int s=1;
while(b)
{
if(b&1)s=1ll*s*a%P;
b>>=1;
a=1ll*a*a%P;
}
return s;
}
void init(int len)
{
int l=0;
lim=1;
while(lim<=len)lim<<=1,l++;
int wn=fsp(g,(P-1)/lim),cw=fsp(gi,(P-1)/lim);
w[0]=c[0]=1;
for(int i=1;i<lim;i++)
{
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
w[i]=1ll*w[i-1]*wn%P;
c[i]=1ll*c[i-1]*cw%P;
}
}
void NTT(int num[],int typ)
{
for(int i=0;i<lim;i++)if(i<r[i])swap(num[i],num[r[i]]);
if(typ==1)
{
for(int m=1,t=(lim>>1);m<lim;m<<=1,t>>=1)
{
for(int i=0;i<lim;i+=(m<<1))
{
for(int j=0;j<m;j++)
{
int x=num[i+j],y=1ll*num[i+j+m]*w[t*j]%P;
num[i+j]=(x+y)%P;
num[i+j+m]=(x-y+P)%P;
}
}
}
}else{
for(int m=1,t=(lim>>1);m<lim;m<<=1,t>>=1)
{
for(int i=0;i<lim;i+=(m<<1))
{
for(int j=0;j<m;j++)
{
int x=num[i+j],y=1ll*num[i+j+m]*c[t*j]%P;
num[i+j]=(x+y)%P;
num[i+j+m]=(x-y+P)%P;
}
}
}
int invlen=fsp(lim);
for(int i=0;i<lim;i++)
{
num[i]=1ll*num[i]*invlen%P;
}
}
}
void poly_mul(int a[],int b[],int len)
{
init(len);
NTT(a,1),NTT(b,1);
for(int i=0;i<lim;i++)a[i]=1ll*a[i]*b[i]%P;
NTT(a,-1);
}
void poly_inv(int a[],int b[],int len)
{
int tmp[maxn];
b[0]=fsp(a[0]);
int op=1,ln=1;
while(ln<=(len<<1))
{
init(ln);
for(int i=0;i<ln;i++)tmp[i]=a[i];
NTT(tmp,1),NTT(b,1);
for(int i=0;i<lim;i++)b[i]=1ll*(1ll*2*b[i]-1ll*b[i]*b[i]%P*tmp[i]%P+P)%P;
NTT(b,-1);
for(int i=ln;i<lim;i++)b[i]=0;
ln<<=1;
}
}
int a[maxn],b[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
poly_inv(a,b,n);
for(int i=0;i<n;i++)
{
cout<<b[i]<<" ";
}
return 0;
}