差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:tle233:polynomial [2020/05/23 21:10]
marvolo
+++ 2020-2021:teams:tle233:polynomial [2020/05/23 21:16] (当前版本)
marvolo
@@ 行 127: / 行 127: @@
 }
 </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})$$
+题解:
+多项式大杂烩,套一下上面的板子就行了.

CVBB ACM Team

用户工具

站点工具

差别

页面工具