[学习笔记] 多项式全家桶系列
题外话：
本来这段时间都在洛谷写博客的…
但是因为洛谷猝不及防的改版了导致洛谷博客的搜索功能一度变的很垃圾..
所以又回来了…
等什么时候变好了再回去吧…
哦对了我去洛谷写博客的唯一理由是自己高兴。嗯，真的。
多项式全家桶系列
本来觉得这些没啥用，但是想学新东西了…那就随便学学叭
多项式求逆
Description
给定多项式 \(F(x)\)，请求出一个多项式 \(G(x)\)，满足 \(F(x)G(x)\equiv 1\; \operatorname{mod} x^n\)。对 \(998244353\) 取模。
Sol
推导过程挺简单也挺显然的…
结论就是 \[B(x)\equiv 2B'(x)-A(x)B’^2(x)\; \operatorname{mod} x^n\]
其中 \[A(x)B'(x)\equiv 1\; \operatorname{mod} x^{\frac n2}\]
一个多项式有没有逆取决于常数项有没有逆
Code
void solve(int len){
if(len==1) return b[0]=inv(a[0]),void();
solve(len>>1);lim=len+len;
for(int i=1;i<lim;i++) rev[i]=(rev[i>>1]>>1)|(i&1?lim>>1:0);
for(int i=0;i<len;i++) c[i]=a[i];
ntt(c,1);ntt(b,1);
for(int i=0;i<lim;i++) b[i]=(2ll*b[i]%mod-1ll*c[i]*b[i]%mod*b[i]%mod+mod)%mod;
ntt(b,-1);
for(int i=0;i<lim;i++) c[i]=0;
for(int i=len;i<lim;i++) b[i]=0;
}多项式除法
Description
给出 \(n\) 次多项式 \(F(x)\) 和 \(m\) 次多项式 \(G(x)\)，请求出多项式 \(Q(x),R(x)\)，满足:
- \(deg(Q)=n-m,deg(R)<m\)
- \(F(x)=G(x)Q(x)+R(x)\)
对 \(998244353\) 取模。
Sol
首先，对于任意多项式
\[P(x)=\sum_{i=0}^na_ix^i\]
显然有
\[P^{rev}(x)=x^nP(\frac 1x)=\sum_{i=0}^na_{n-i}x^i\]
也就是说通过这个可以把多项式的系数翻转。
对 \(F(x)=G(x)Q(x)+R(x)\) 进行这个操作：
\[F(x)=G(x)Q(x)+R(x)\]
\[F(\frac 1x)=G(\frac 1x)Q(\frac 1x)+R(\frac 1x)\]
\[x^nF(\frac 1x)=x^nG(\frac 1x)Q(\frac 1x)+x^nR(\frac 1x)\]
\[x^nF(\frac 1x)=x^mG(\frac 1x)x^{n-m}Q(\frac 1x)+x^{n-m+1}x^{m-1}R(\frac 1x)\]
\[F^{rev}(x)=G^{rev}(x)Q^{rev}(x)+x^{n-m+1}R^{rev}(x)\]
注意到 \(x^{n-m+1}R^{rev}(x)\) 的最低项次数至少为 \(n-m+1\)，所以我们对式子取模：
\[F^{rev}(x)=G^{rev}(x)Q^{rev}(x)\; \operatorname{mod}x^{n-m+1}\]
因为 \(deg(Q)=n-m\)，所以这样是不会出问题的。
所以就可以算出 \(Q^{rev}(x)=F^{rev}(x)(G^{rev}(x))^{-1}\)
多项式求逆即可。
整个做法的关键就是消去余数。
Code
void solve(){
n=getint(),m=getint();
for(int i=0;i<=n;i++) f[i]=getint();
for(int i=0;i<=m;i++) g[i]=getint();
std::reverse(f,f+n+1),std::reverse(g,g+m+1); //翻转系数
for(int i=0;i<=n-m;i++) ing[i]=g[i];
//因为对 x^{n-m+1} 取模，所以后边的系数都应该为0
getni(ing,q,n-m+1); //求出g的逆q
for(int i=0;i<=n-m;i++) c[i]=f[i]; //后边的系数都应该为0
mul(q,c,n-m+1);
for(int i=0;i<lim;i++) c[i]=0;
std::reverse(q,q+n-m+1);
for(int i=0;i<=n-m;i++) printf("%d ",q[i]);puts("");
for(int i=n-m+1;i<lim;i++) q[i]=0;
std::reverse(f,f+n+1),std::reverse(g,g+m+1);
mul(q,g,n);
for(int i=0;i<m;i++) printf("%d ",(f[i]-q[i]+mod)%mod);
}多项式开根
Description
给定多项式 \(A(x)\)，若存在一个多项式 \(B(x)\),满足：
- \(deg(B)\leq deg(A)\)
- \(B^2(x)\equiv A(x)\;\operatorname{mod} x^n\)
则称 \(B(x)\) 为 \(A(x)\) 在模 \(x^n\) 意义下的开根。
Sol
懒得写了…
感谢AlphaINF
三模数NTT
Description
求 \(F(x)G(x)\)，对 \(p\) 取模。\(p\) 不保证有原根。
Sol
拆成对三个模数 \(469762049,998244353,1004535809\) 分别做 \(NTT\)，它们的原根都是 \(3\)。
先合并前两个式子，得到:
\[ans\equiv C\;\operatorname{mod}M\]
\[ans\equiv c_3\operatorname{mod} m_3\]
设:
\[ans=xM+C=ym_3+c_3\]
求出 \(x\) 在 \(\operatorname{mod}m_3\) 意义下的值：
\[xM\equiv c_3-C\;\operatorname{mod}m_3\]
在 \(\operatorname{mod} m_3\) 意义下， \(ym_3\) 被消掉了。所以有：
\[x\equiv (c_3-C)M^{-1}\;\operatorname{mod}m_3\]
算出右边的值为 \(q\),令 \(x=km_3+q\)，代入\(ans=xM+C\):
\[ans=(km_3+q)M+C=km_1m_2m_3+qM+C\]
因为 \(ans\in[0,m_1m_2m_3)\)，所以 \(k=0\)！ 所以 \(ans=qM+C\)！
Code
主要是合并部分
int get(int x,int y,int z,int mod){
ll M=p[1]*p[0];
ll tmp1=mul(1ll*x*p[1]%M,inv(p[1]%p[0],p[0]),M); //快速幂之前先取模
ll tmp2=mul(1ll*y*p[0]%M,inv(p[0]%p[1],p[1]),M);
ll tmp=(tmp1+tmp2)%M;
ll xx=1ll*(z-tmp%p[2]+p[2])%p[2]*inv(M%p[2],p[2])%p[2];
return ((xx%mod)*(M%mod)%mod+tmp%mod)%mod; //注意这里先对mod取模再乘起来
}多项式exp，ln等学完高数马上填坑
多项式对数函数
Description
给定 \(n-1\) 次多项式 \(A(x)\)，求一个 \(\bmod x^n\) 下的多项式 \(B(x)\)，满足 \(B(x)\equiv \ln A(x)\;\bmod x^n\)。对 \(998244353\) 取模。
Sol
求ln还是挺傻逼的吧…
根据微积分基本知识，复合函数 \(y=f(g(x))\) 的导数和函数 \(y=f(u),u=g(x)\) 的导数间的关系为:
\[y_x’=y_u’\cdot u_x’\]
然后这题就是求 \(y=\ln(A(x))\)
根据上边的定义转变成 \(y’=\frac{A'(x)}{A(x)}\)
求导求逆再积分就行了
然后发现自己求逆的一点小bug就是设置长度设置为不小于 \(n\) 的 \(2\) 的整次幂就行了，不用大于 \(2n\)。
void ds(int *a,int *b,int n){
for(int i=1;i<n;i++) b[i-1]=1ll*a[i]*i%mod;b[n-1]=0;
}
void jf(int *a,int *b,int n){
for(int i=1;i<n;i++) b[i]=1ll*a[i-1]*inv(i)%mod;b[0]=0;
}
void getln(int *f,int *g,int lim){
getinv(f,d,c);
for(int i=1;i<lim;i++) rev[i]=(rev[i>>1]>>1)|(i&1?lim>>1:0);
ds(f,b,lim);
ntt(b,1),ntt(d,1);
for(int i=0;i<lim;i++) b[i]=1ll*b[i]*d[i]%mod;
ntt(b,-1);jf(b,g,lim);
}