洛谷P4238 多项式乘法逆元

大家好，我是讯享网，很高兴认识大家。

模板：多项式乘法逆元

给出一个度为 $n - 1$ 的多项式 $f (x)$ ，求一个度为 $n - 1$ 的 $g (x)$ ，使得 $f(x)\cdot g(x) \equiv1\ (mod\ x^n)$

这里的多项式 $mod\ x^k$ 的意思是舍弃掉所有次数 $\geq k$ 的项后的多项式

Solution：

多项式的操作似乎都是分治解决的

若我们找到一个 $t (x)$ ，使得

$f(x)\cdot t(x)\equiv 1\ (mod\ x^{\lceil\frac{n}{2}\rceil})\tag{1}$

因为

$f(x)\cdot g(x)\equiv1\ (mod\ x^{n})$

于是有

$f(x)\cdot g(x)\equiv1\ (mod\ x^{\lceil\frac{n}{2}\rceil})\tag{2}$

将 $(1)$ 与这个式子做差，有

$f(x)\cdot(t(x)-g(x)) \equiv0\ (mod\ x^{\lceil\frac{n}{2}\rceil})$

讯享网

由于 $f (x)$ 不可能为0，于是

$t(x)-g(x)\equiv0\ (mod\ x^{\lceil\frac{n}{2}\rceil})$

两边平方并移项有

$g^{2}(x)\equiv2\cdot t(x) \cdot g(x)-t^{2}(x)\ (mod\ x^{\lceil\frac{n}{2}\rceil})$

左右两边乘 $f (x)$ ，得到

$f(x)\cdot g^{2}(x)\equiv2\cdot f(x)\cdot t(x) \cdot g(x)-f(x)\cdot t^{2}(x)\ (mod\ x^{\lceil\frac{n}{2}\rceil})$

由 $(1) (2)$ 两式，代入得到

$g(x)\equiv 2\cdot t(x)-f(x)\cdot t^{2}(x)\ (mod\ x^{\lceil\frac{n}{2}\rceil})\tag{3}$

于是我们求 $g (x)$ 可以先求 $t (x)$ ，求 $t (x)$ 可以先求 $(mod\ x^{\lceil\frac{n}{4}\rceil})$ ，递归出口即求 $(mod\ x)$ ，此时只剩常数项，多项式逆元就是常数项逆元

tips:

$(3)$ 式递推时不需要多次ntt，我们只要把他们转换为点值式后直接运算就可以了，不过需要注意的是，这里面发生了三个多项式相乘，因此相乘时 $l imi t$ 要设为大于三个多项式的度总和的一个2的幂

// #include<bits/stdc++.h> #include<iostream> #include<cstdio> using namespace std; using ll=long long; const int N=,inf=0x3fffffff; const long long INF=0x3f3f3f3f3f3f,mod=,inv3=; int getlen(int k) { 
    int ret=0; while(k){ 
   ret++;k>>=1;} return ret; } int getrev(int k,int len) { 
    int ret=0; while(k){ 
   ret=(ret<<1|(k&1));k>>=1;len--;} return ret<<len; } ll qpow(ll a,ll b) { 
    ll ret=1,base=a; while(b) { 
    if(b&1) ret=ret*base%mod; base=base*base%mod; b>>=1; } return ret; } ll inv(ll k){ 
   return qpow(k,mod-2);} int pos[N]; void ntt(ll *a,int limit,int op) { 
    for(int i=0;i<limit;i++) if(i<pos[i]) swap(a[i],a[pos[i]]); for(int len=2;len<=limit;len<<=1) { 
    ll base=qpow(op==1?3:inv3,(mod-1)/len); for(int l=0;l<limit;l+=len) { 
    ll now=1; for(int i=l;i<l+len/2;i++) { 
    ll x=a[i]%mod,y=now*a[i+len/2]%mod; a[i]=(x+y)%mod; a[i+len/2]=(x-y+mod)%mod; now=now*base%mod; } } } } ll a[N],b[N]; inline void multi(ll *f,ll* g,int n,int m)//f*=g { 
    int limit=1; while(limit<=n+2*m) limit<<=1;//此处式n+2*m，三个多项式相乘了 int len=getlen(limit-1); for(int i=0;i<limit;i++) { 
    pos[i]=getrev(i,len); a[i]=f[i]; b[i]=g[i]; } ntt(a,limit,1); ntt(b,limit,1); for(int i=0;i<limit;i++) a[i]=b[i]*((2-a[i]*b[i]%mod)%mod+mod)%mod; ntt(a,limit,-1); ll tmp=inv(limit); for(int i=0;i<limit;i++) f[i]=a[i]*tmp%mod; } int n,nn; ll f[N],g[N],t[N]; void solve(int len) { 
    if(len==1){ 
   t[0]=inv(f[0]);return;} solve(len+1>>1);//此处一定要Len/2上取整 for(int i=0;i<n;i++) g[i]=f[i]; multi(g,t,n,len+1>>1); for(int i=0;i<len;i++) t[i]=g[i]; for(int i=len;i<n+2*(len+1>>1);i++) g[i]=t[i]=0; } int main() { 
    cin>>n; for(int i=0;i<n;i++) cin>>f[i]; solve(n); for(int i=0;i<n;i++) printf("%lld ",g[i]); return 0; }

讯享网

洛谷P4238 多项式乘法逆元

模板：多项式乘法逆元

Solution：

tips:

相关推荐