这里会显示出您选择的修订版和当前版本之间的差别。
后一修订版 | 前一修订版 | ||
2020-2021:teams:tle233:polynomial [2020/05/17 09:20] marvolo 创建 |
2020-2021:teams:tle233:polynomial [2020/05/23 21:16] (当前版本) marvolo |
||
---|---|---|---|
行 1: | 行 1: | ||
- | ==== 多项式求逆 ==== | + | ====== 多项式求逆 ====== |
- | === 定义 === | + | ===== 定义 ===== |
- | 对于一个多项式$A(x)$,如果存在另一个多项式$B(x)$,有$deg B(x) deg A(x) $,且$A(x)B(x) (x<sup>{n})$,那么称$B(x)$为$A(x)$在$x</sup>{n}$下的逆元,记为$A^{-1}(x)$ | + | 对于一个多项式$A(x)$,如果存在另一个多项式$B(x)$,有$deg B(x) \leq deg A(x) $,且$A(x)B(x) \equiv 1 (\mod x^{n})$,那么称$B(x)$为$A(x)$在$\mod x^{n}$下的逆元,记为$A^{-1}(x)$ |
- | === 求法 === | + | ===== 求法 ===== |
当$n=1$时,$A(x) \equiv c (\mod x)$,此时$A^{-1}(x) \equiv c^{-1}$ | 当$n=1$时,$A(x) \equiv c (\mod x)$,此时$A^{-1}(x) \equiv c^{-1}$ | ||
行 21: | 行 21: | ||
于是就可以根据最后一个式子递归计算了.在计算的时候需要拿NTT来实现多项式乘法的过程.总的时间复杂度为$O(n\log n)$. | 于是就可以根据最后一个式子递归计算了.在计算的时候需要拿NTT来实现多项式乘法的过程.总的时间复杂度为$O(n\log n)$. | ||
- | === 代码模板 === | + | ===== 代码模板 ===== |
<code cpp> | <code cpp> | ||
行 40: | 行 40: | ||
</code> | </code> | ||
- | ==== 多项式除法和取模 ==== | + | ====== 多项式除法和取模 ====== |
- | === 求法 === | + | ===== 求法 ===== |
给出两个多项式$F(x)$,$G(x)$,求$D(x)$,$R(x)$,使得$F(x)=D(x)G(x)+R(x)$.其中,$F(x)$为$n$次多项式,$G(x)$为$m$次多项式,$m \leq n$.要求求出的$D(x)$为$n-m $次多项式. | 给出两个多项式$F(x)$,$G(x)$,求$D(x)$,$R(x)$,使得$F(x)=D(x)G(x)+R(x)$.其中,$F(x)$为$n$次多项式,$G(x)$为$m$次多项式,$m \leq n$.要求求出的$D(x)$为$n-m $次多项式. | ||
行 64: | 行 64: | ||
然后利用上面的求逆元过程,算出$D^{r}(x)$,翻转就可以得到$D(x)$了.然后带回到原式,就可以算出$R(x)$.总的时间复杂度也是$O(n \log n)$. | 然后利用上面的求逆元过程,算出$D^{r}(x)$,翻转就可以得到$D(x)$了.然后带回到原式,就可以算出$R(x)$.总的时间复杂度也是$O(n \log n)$. | ||
- | === 代码模板 === | + | ===== 代码模板 ===== |
<code cpp> | <code cpp> | ||
行 90: | 行 90: | ||
} | } | ||
</code> | </code> | ||
+ | |||
+ | |||
+ | ====== 多项式开根 ====== | ||
+ | |||
+ | 假如说求$B(x)$,使得$B(x)^{2} \equiv A(x) (\mod x^{n})$.不妨设$B'(x)^{2} \equiv A(x) (\mod x^{\lceil \frac{n}{2} \rceil})$.同时,已知$B(x)^{2} \equiv A(x) (\mod x^{\lceil \frac{n}{2} \rceil})$. | ||
+ | |||
+ | 两个等式相减,再平方,可得$B'(x)^{4}-2B'(x)^{2}B(x)^{2}+B(x)^{4} \equiv 0 (\mod x^{n})$ | ||
+ | |||
+ | 做一下变形,有$B'(x)^{4}+2B'(x)^{2}B(x)^{2}+B(x)^{4} \equiv 4B'(x)^{2}B(x)^{2} (\mod x^{n})$ | ||
+ | |||
+ | 故有$B'(x)^{2}+B(x)^{2}\equiv 2B(x)B'(x) (\mod x^{n})$ | ||
+ | |||
+ | 将已知条件代入,有$B(x) \equiv \frac{A(x)+B'(x)^{2}}{2B'(x)}$ | ||
+ | |||
+ | 和多项式求逆那样递归计算即可. | ||
+ | |||
+ | 有一个问题是,当递归到$n=1$的时候,要求常数项在模意义下开根.洛谷上的例题规定了常数项一定为1,所以保证有解.如果不规定常数项的话,还需要通过二次剩余来判断解的存在性. | ||
+ | |||
+ | ===== 代码模板 ===== | ||
+ | |||
+ | **注意数组大小要开到8倍以上.** | ||
+ | |||
+ | <code cpp> | ||
+ | IL void PolySqrt(LL a[],LL b[],int len){ | ||
+ | reg int i=0; | ||
+ | if (len==1){ | ||
+ | b[0]=1; return; | ||
+ | } | ||
+ | PolySqrt(a,b,(len+1)>>1); | ||
+ | memset(e,0,sizeof(e)); | ||
+ | for (i=0;i<len;i++) c[i]=(b[i]<<1)%MOD; | ||
+ | PolyInv(c,e,len); | ||
+ | PolyMul(b,b,d,len,len); | ||
+ | for (i=0;i<len;i++) b[i]=(d[i]+a[i])%MOD; | ||
+ | PolyMul(b,e,b,len,len); | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | ====== 多项式求导&积分 ====== | ||
+ | |||
+ | 原理应该不用多讲了…直接算就行了,积分的时候除上逆元. | ||
+ | |||
+ | ===== 代码模板 ===== | ||
+ | |||
+ | <code cpp> | ||
+ | IL void PolyDx(LL a[],LL b[],LL len){ | ||
+ | reg LL i=0; | ||
+ | for (i=0;i<=len;i++) b[i]=(a[i+1]*(i+1))%MOD; | ||
+ | } | ||
+ | |||
+ | IL void PolyInte(LL a[],LL b[],LL len){ | ||
+ | reg LL i=0; | ||
+ | b[0]=0; | ||
+ | for (i=1;i<=len;i++) | ||
+ | b[i]=(a[i-1]*Mi(i,MOD-2))%MOD; | ||
+ | } | ||
+ | </code> | ||
+ | ====== 多项式Ln ====== | ||
+ | |||
+ | 给出$A(x)$,求$B(x)$,使得$B(x) \equiv ln(A(x)) (\mod x^{n})$ | ||
+ | |||
+ | 对原式两边求导,有$B'(x) \equiv \frac{A'(x)}{A(x)} (\mod x^{n})$ | ||
+ | |||
+ | 通过多项式的求导和求逆算出$B'(x)$后,再积分即可得到$B(x)$. | ||
+ | |||
+ | ===== 代码模板 ===== | ||
+ | |||
+ | <code cpp> | ||
+ | IL void PolyLn(LL a[],LL b[],LL len){ | ||
+ | PolyDx(a,d,len); | ||
+ | PolyInv(a,c,len); | ||
+ | PolyMul(d,c,d,len,len); | ||
+ | PolyInte(d,b,len); | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | ====== 多项式Exp ====== | ||
+ | |||
+ | 需要一些多项式牛顿迭代的基础. | ||
+ | |||
+ | 求一个多项式$G(x)$,使得$F(G(x)) \equiv 0 (\mod x^{n})$.如果说已经求出来了$F(G_{0}(x)) \equiv 0 (\mod x^{\lceil \frac{n}{2} \rceil})$,将$F(G(x))$在$G_{0}(x)$处展开,因为$G(x)-G_{0}(x)$的最低次数已经是$\lceil \frac{n}{2} \rceil$了,所以这一项平方之后,在模$x^{n}$意义下为0.故泰勒展开只需要保留前两项,也就是: | ||
+ | |||
+ | $F(G(x)) = F(G_{0}(x)) +(G(x)-G_{0}(x))F'(G_{0}(x)) \equiv 0 (\mod x^{n})$ | ||
+ | |||
+ | 其中的$F'(x)$表示一阶导.化简,有$G(x) \equiv G_{0}(x)-\frac{F(G_{0}(x))}{F'(G_{0}(x))} (\mod x^{n})$. | ||
+ | |||
+ | 然后回到这个问题上.现在是要求$B(x) \equiv e^{A(x)} (\mod x^{n})$.两边求对数,化简,有$ln(B(x))-A(x) \equiv 0 (\mod x^{n})$. | ||
+ | |||
+ | 这个时候,构造$F(G(x))=lnG(x)-A(x)$.利用牛顿迭代不断求解就行了. | ||
+ | |||
+ | 式子的话,$(F(G(x)))'=\frac{G'(x)}{G(x)}$.把它带到迭代 的式子中,化简一下就有$G(x)=G_{0}(x)-\frac{G_{0}(x)(1-lnG_{0}(x)+A(x))}{G'_{0}(x)}$ | ||
+ | |||
+ | 最后根据上面这个式子就可以递归计算了. | ||
+ | |||
+ | **因为要多次算Ln,所以中间用到的两个数组需要清空一下** | ||
+ | |||
+ | 不知道哪个环节有问题,这个板子的常数极大,而且是别人平均时间的两倍左右…有待优化. | ||
+ | |||
+ | <code cpp> | ||
+ | IL void PolyLn(LL a[],LL b[],LL len){ | ||
+ | PolyDx(a,d,len); | ||
+ | PolyInv(a,c,len); | ||
+ | PolyMul(d,c,d,len,len); | ||
+ | PolyInte(d,b,len); | ||
+ | for (LL i=0;i<=len;i++) c[i]=d[i]=0; | ||
+ | } | ||
+ | |||
+ | IL void PolyExp(LL a[],LL b[],LL len){ | ||
+ | reg LL i=0; | ||
+ | if (len==1){ | ||
+ | b[0]=1; return; | ||
+ | } | ||
+ | PolyExp(a,b,len>>1); | ||
+ | for (i=0;i<=len;i++) e[i]=0; | ||
+ | PolyLn(b,e,len); | ||
+ | for (i=0;i<len;i++) | ||
+ | e[i]=(((i==0)?1:0)-e[i]+a[i]+MOD)%MOD; | ||
+ | PolyMul(b,e,b,len,len); | ||
+ | } | ||
+ | |||
+ | </code> | ||
+ | |||
+ | ====== 多项式快速幂 ====== | ||
+ | |||
+ | 会了求导和求对数之后就很简单了. | ||
+ | |||
+ | $B(x) \equiv A(x)^{k}$,求导,有$lnB(x) \equiv klnA(x)$. | ||
+ | |||
+ | 求导,乘以$k$,再exp回去就行了. | ||
+ | |||
+ | ===== 代码模板 ===== | ||
+ | |||
+ | 因为同时使用了对数和指数的原因,常数极大. | ||
+ | |||
+ | <code cpp> | ||
+ | IL void PolyMi(LL a[],LL b[],LL len,LL k){ | ||
+ | reg int i=0; | ||
+ | PolyLn(a,p,len); | ||
+ | for (i=0;i<=len;i++) p[i]=(p[i]*k)%MOD; | ||
+ | PolyExp(p,b,len); | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | ====== 多项式三角函数 ====== | ||
+ | |||
+ | 根据著名的欧拉公式:$e^{ix}=\cos x+i\sin x$.代入正负$x$,然后解方程,有: | ||
+ | |||
+ | $\sin x=\frac{e^{ix}-e^{-ix}}{2i}$ | ||
+ | |||
+ | $\cos x=\frac{e^{ix}+e^{-ix}}{2}$ | ||
+ | |||
+ | 然后就是一波玄学操作:$i^{2}=-1$,$i^{2} \equiv -1 (\mod 998244353)$,$i \equiv 86583718 (\mod 998244353)$,$i^{-1} () $ | ||
+ | |||
+ | 分子分母上的$i$就搞定了. | ||
+ | |||
+ | <del>没学过复变,但是感觉复变老师看到这一段可能想打人</del> | ||
+ | |||
+ | ===== 代码模板 ===== | ||
+ | |||
+ | 这里参考大佬的博客给NTT加了一个预处理的优化,但是效果不是特别理想. | ||
+ | |||
+ | <code cpp> | ||
+ | IL void Ready(){ | ||
+ | reg LL i=0; | ||
+ | for (i=2;i<=800000;i<<=1) | ||
+ | Wn[i]=Mi(3,(MOD-1)/i),WN[i]=Mi(Wn[i],MOD-2); | ||
+ | } | ||
+ | </code> | ||
+ | 所以还是依靠O2,O3优化靠谱一些.慎重使用这个板子吧. | ||
+ | |||
+ | <code cpp> | ||
+ | IL void PolySin(LL a[],LL b[],LL len){ | ||
+ | reg LL i=0,u=86583718,invu=Mi(u,MOD-2),inv2=Mi(2,MOD-2),inv=0; | ||
+ | for (i=0;i<=len;i++) a[i]=(a[i]*u)%MOD; | ||
+ | PolyExp(a,p,len); PolyInv(p,b,len); | ||
+ | inv=(inv2*invu)%MOD; | ||
+ | for (i=0;i<=len;i++) b[i]=(p[i]-b[i]+MOD)%MOD; | ||
+ | for (i=0;i<=len;i++) b[i]=(b[i]*inv)%MOD; | ||
+ | } | ||
+ | |||
+ | IL void PolyCos(LL a[],LL b[],LL len){ | ||
+ | reg LL i=0,u=86583718,invu=Mi(u,MOD-2),inv2=Mi(2,MOD-2); | ||
+ | for (i=0;i<=len;i++) a[i]=(a[i]*u)%MOD; | ||
+ | PolyExp(a,p,len); PolyInv(p,b,len); | ||
+ | for (i=0;i<=len;i++) b[i]=(p[i]+b[i])%MOD; | ||
+ | for (i=0;i<=len;i++) b[i]=(b[i]*inv2)%MOD; | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | ====== 多项式反三角函数 ====== | ||
+ | |||
+ | 首先,有 | ||
+ | |||
+ | $\frac{d}{dx}\arcsin x=\frac{1}{\sqrt{1-x^{2}}}$ | ||
+ | |||
+ | $\frac{d}{dx}\arctan x=\frac{1}{1+x^{2}}$ | ||
+ | |||
+ | 根据这个式子,将多项式代入,再积分,就有 | ||
+ | |||
+ | $B(x)=\int \frac{A'(x)}{\sqrt{1-A'(x)^{2}}}$ | ||
+ | |||
+ | $B(x)=\int \frac{A'(x)}{1+A'(x)^{2}}$ | ||
+ | |||
+ | 所以只需要多项式求导,求逆,开根,积分就能完成反三角函数的求解. | ||
+ | |||
+ | ===== 代码模板 ===== | ||
+ | |||
+ | <code cpp> | ||
+ | IL void PolyArcsin(LL a[],LL b[],LL len){ | ||
+ | reg int i=0; | ||
+ | PolyDx(a,p,len); | ||
+ | PolyMul(a,a,q,len,len); | ||
+ | for (i=0;i<=len;i++) q[i]=(MOD-q[i])%MOD; | ||
+ | q[0]=Upd(q[0]+1-MOD); | ||
+ | PolySqrt(q,w,len); | ||
+ | memset(q,0,sizeof(q)); | ||
+ | PolyInv(w,q,len); PolyMul(p,q,p,len,len); | ||
+ | PolyInte(p,b,len); | ||
+ | } | ||
+ | |||
+ | IL void PolyArctan(LL a[],LL b[],LL len){ | ||
+ | PolyDx(a,p,len); | ||
+ | PolyMul(a,a,q,len,len); | ||
+ | q[0]=(q[0]+1)%MOD; | ||
+ | PolyInv(q,w,len); PolyMul(p,w,p,len,len); | ||
+ | PolyInte(p,b,len); | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | ====== 例题 ====== | ||
+ | |||
+ | 洛谷上有上面各个模板的板子题,直接搜多项式就能找到. | ||
+ | |||
+ | 还有一道综合些的题目:[[https://loj.ac/problem/150|LOJ 挑战多项式]] | ||
+ | |||
+ | 题意:求 | ||
+ | |||
+ | $$G(x) \equiv ((1+ln(2+F(x)-F(0)-exp(\int _{0}^{x}\frac{1}{\sqrt{F(x)}})))^{k})' (\mod x^{n})$$ | ||
+ | |||
+ | 题解: | ||
+ | |||
+ | 多项式大杂烩,套一下上面的板子就行了. | ||
+ | |||