给定一个多项式 (F(x)) ，请求出一个多项式 (G(x))， 满足 (F(x) * G(x) equiv 1 ( mathrm{mod:} x^n ))。系数对 (998244353) 取模。
考虑倍增
多项式只有一项时就是乘法逆元
假设我们现在得到了
[G^{'}(x) equiv F(x) (mod x^{frac{n}{2}})
]
我们需要求
[G(x)equiv F(x) (mod x^n)
]
很明显
[G(x)-G^{'}(x)equiv 0 (mod x^{frac{n}{2}})
]
两边同时平方
[G(x)^2-2*G(x)G^{'}(x)+G^{'}(x)equiv 0 (mod x^n)
]
两边同时乘(F(x))得到
[F(x)(G(x)^2-2*G(x)G^{'}(x)+G^{'}(x))equiv 0 (mod x^n)
]
[F(x)G(x)equiv 1(mod x^n)
]
[G(x)-2G(x)^{'}+F(x)G^{'2}(x)equiv (mod x^n)
]
移下项
[G(x)equiv 2G(x)^{'}-F(x)G^{'2}(x)(mod x^n)
]
只要初始设置(G(0)=F(0)^{-1})就可以倍增啦～
额额额不知道有没有人和我有一样的疑惑：为啥递归一次多项式次数少一半，原因是模掉了……
#include
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
inline int read()
{
for(ch=getchar();(ch'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=5e5+10,p=998244353,g=3,gi=332748118;
inline int fast(int x,int k)
{
while(k)
{
if(k&1) ret=ret*x%p;
x=x*x%p;
k>>=1;
}
return ret;
}
inline void ntt(int limit,int *a,int inv)
{
for(int i=0;i
if(i
for(int mid=1;mid
{
for(int r=mid<<1,j=0;j
{
for(int k=0;k
{
a[j+k]=x+y;
if(a[j+k]>=p) a[j+k]-=p;
a[j+k+mid]=x-y;
if(a[j+k+mid]<0) a[j+k+mid]+=p;
}
}
}
if(inv) return;
inv=fast(limit,p-2);reverse(a+1,a+limit);
for(int i=0;i
}
inline void poly_inv(int pw,int *a,int *b)
{
if(pw==1) {b[0]=fast(a[0],p-2);return;}
poly_inv((pw+1)>>1,a,b);
while(limit
for(int i=1;i>1]>>1)|((i&1)<
for(int i=0;i
for(int i=pw;i
ntt(limit,c,1);ntt(limit,b,1);
for(int i=0;i
ntt(limit,b,0);
for(int i=pw;i
}
inline void main()
{
n=read();
for(int i=0;i
poly_inv(n,a,b);
for(int i=0;i
}
}
signed main()
{
red::main();
return 0;
}