Newuser

【MOBAN】多项式算法模板和小记录

多项式乘法,多项式求逆,多项式除法,多项式开方,多项式求导和积分,多项式取模,多项式指数函数,多项式对数函数,多项式快速幂,多项式多点求值,多项式多点插值,常系数线性递推,多项式求复合逆,拆系数FFT

 

参考文章:https://blog.csdn.net/kscla/article/details/79356786

预备

不用long long 多件套和LJ NTT

多项式乘法

 

多项式求逆:

求A(x)*B(x)==1(mod x^n)

设定A(x)*G(x)==1(mod x^(n/2)

那么就有B(x) – G(x) == 0 (mod x^(n/2) )

就有B(x)^2 + G(x)^2 – 2B(x)G(x) == 0 (mod x^(n))

两边同乘上A,就最终可以得到 B(x) = G(x)(2-AG(x))了

多项式除法

我们设定Ar(x) = x^n*A(1/x)

比如举个例子A(x) = x^3 + 2x^2 + 4x + 1 Ar(x) = 1+2x+4*x^3+x^3 这恰好等于A(x)的系数反转。

考虑原式我们只要将x替换成1/x,会发现一些有趣的事情。 F(1/x)x^n == Q(1/x)G(1/x)x^n + x^nR(x) Fr(x) = Qr(x) + Gr(x) + Rr(x)x^(n-m+1) 那么Ar(x) == Dr(x)Br(x) ( mod x^(n-m+1))

 

多项式取模(源自多项式除法)

我们已知除数和商和被除数,那么余就等于被除数-商×除数

 

多项式开方

考虑和多项式求逆用到的同样的倍增的方法

如果我已知B(x)*B(x) == A(x) mod(x^m)

求C(x)使得C(x)C(x) == A(x) mod(x^(2m))

则(B(x)+C(x))*(B(x)-C(x))==0(mod x^(m))

那么我们讨论B(x)-C(x)==0情况

最后又可以得到C(x)==(A(x)+B(x)^2)/(2*B(x)) (mod x^(2m))

code://代入a,b^2 = a

多项式求导和积分

有关微积分的参考:

某博客https://www.cnblogs.com/zwfymqz/p/9127894.html

高中数学书选修2-2 http://jiaofu.yousi.com/compontent/pdf/?url=http://jfpdf.yousi.com/160424030303585634.pdf#page=11]

 F(x) = \sum_{i=0}^{n}a_{i} * x^i

 F'(x) = \sum_{i=1}^{n} i * a_{i} * x^{i-1}

 \int F(x) = \sum_{i=1}^{n} \frac{a_{i}* x^{i+1} }_{i+1}

所以我们如果把多项式看做一个函数就可以求导和积分了。

多项式对数函数

给出 n-1 次多项式 A(x),求一个mod x^n下的多项式B(x)==ln A(x)

我们知道\ln x的导数为\frac{1}{x},我们设F(x) = \ln x

B(x) = F(A(x))

B(x)\prime = F(A(x))\prime * A(x)\prime

B(x) = \int \frac {A\prime}{A}

直接代入搞就可以了

多项式指数指数

已知函数F,求G==e^F (mod)

由于牛顿迭代公式

xi= xi-1 – f(xi-1) / f ‘ (xi-1)

那么初始x0 = ea0  

显然只有a0等于0时有意义。

因为lnG – F = 0

套用牛顿迭代公式得到Gi = Gi-1‘(1-lnGi-1‘+F)

就可以搞了。

 

多项式快速幂

啥,直接二分快速幂? 不不不,这是O(nlognlogk)的,他不够优秀

我们知道F(x)^k == exp(ln(F(x)^k)) 并且ln(F(x)^k)==k*ln(F(x)) 我们对多项式求ln,然后系数乘以k之后exp还原就好

注意细节! 我们发现求ln的时候用到的求导和反积分会损失掉常数项! 所以在我们回代回exp之前记得单独处理常数项。

常系数线性递推

求一个满足k阶齐次线性递推数列a_i的第n项。

即:a_n=\sum\limits_{i=1}^{k}f_i \times a_{n-i}

首先矩阵卡速米的做法很显然,把这个递推矩阵写出来,然后直接爆推就可以了。然而k这么大,一次矩阵乘法就GG了。

我们如果能够构造一个数列ci使得 A^{n} = \sum_{i=0}^{k} c_{i} * A_{i} 。但其实我们完全不用真的算出A^n,因为实际上我们想要得到一个递推矩阵,然后最后乘上一个列向量ST(给定的初始那k个数)。

我们把这个向量乘进去 ST * A^{n} = \sum_{i=0}^{k} c_{i} * ST * A_{i} 。我们只需要他最低的那项。我们仔细观察发现这里的ST*Ai的最低项不就是STi吗?所以我们只需要构造出这样一个数列ci,我们就可以得到,答案就是 ANS = \sum_{i=0}^{k-1} c_{i} * ST_{i} 。现在我们考虑怎么构造这个数列。

如果我们把一个这个递推矩阵的特征多项式手算出来:

引入 特征多项式

我们已知对于一个矩阵A,若有非0行(列)向量y,和常数x,使得Ay = xy,那么就称y为A的特征向量,x为A的特征值。我们移一个项,使得|A-Ex|y=0 (E为单位矩阵),由于y行列式不为0,那么一定|A-Ex| = 0 ,同时我们称f(x) = |A-Ex|为矩阵A的特征多项式。由于某个神奇的定理(Cayley-Hamilton定理),f(A) = 0。(啥?你说为什么A是一个矩阵而不是一个常数?我们其实把这个多项式f的x替换成矩阵变量就可以了,感性理解的话|A-A*E| = 0)

所以手算出来后发现,这个多项式恰好是 f(A) = (-1)^{k} * (A^k - \sum_{i=1}^{k} a_{i}*A^{k-i})

由于f(A)==0 , 那么 直接消掉(-1)^{k},得到f(A) = (A^k - \sum_{i=1}^{k} a_{i}*A^{k-i})

也就是说A^n == A^n % (f(A))  , 之后我们就将这个以矩阵为变量的多项式愉快地降低到了次数k-1。也就是说,我们只要构出了这个多项式,也就是我们要的ci数列对应构造出的多项式。多项式取模即可

luogu 线性递推

 

bzoj 4161 O(k^2logn)

多项式多点求值

给定一个n次多项式,现在请你对于,求出

我们考虑分治处理,对于

我们写成一个类似线段树的结构把插值的多项式存下来。

 

多项式多点插值

给定n个点(x1,y1),(x2,y2),(x3,y3)……(xn,yn)求一个n-1次多项式F满足F(xi) = yi

如果我们直接考虑拉格朗日插值就会得到一个n^2的做法

 {F(x)=\sum_{i=1}^n{\frac{\prod_{{j}\neq{i}}{({x}-{x_j})}}{\prod_{{j}\neq{i}}{({x_i}-{x_j})}}{y_i}}}

多项式求复合逆

预备:拉格朗日反演

若两个多项式,都没有常数项,有A(B(x))=x,已知A,称B为A的复合逆。显然若A(B(x))=x则B(A(x)),且一定满足一次项系数互为逆元。

 那么如果已知A要求B的n次项系数,有

[x^n]B(x)=\frac{1}{n} [x^{n-1}] (\frac{x}{A(x)})^{n}

 同时拉格朗日反演有扩展有

[x^n]A(B(x))=\frac{1}{n}[x^{n-1}]A'(x)(\frac{x}{B(x)})^n

就这样我们就可以在nlogn的时间复杂度内完成求解多项式复合逆的某一项系数了

任意模数NTT

由于某些毒瘤出题人出的模数并不棒,想毒瘤一下大家,没法NTT,FFT又精度上有点出事。

多模数NTT

一般对于长度为1e5,数范围在1e9的卷积,可以想到其卷积之后范围应该是大约最大1e23(1e51e91e9)的。

因此我们可以考虑三个1e9左右的模数来NTT之后利用中国剩余定理合并。

把这三个模数背下来吧,因为他们很优秀——原根都是3. 998244353,1004535809,469762049

(1<<26)*7,(1<<23)*119,(1<<21)*479

拆系数FFT

多模数NTT太慢了,那么,快乐的拆系数FFT来啦!

我们把每个数拆成aM+b的形式(M是常数),这样的话,就可以把一个A×B 转化为 (Aa + Ab) × (Ba + Bb)。然后分为三个区域AaBa , AbBa + AaBb,Aa*Bb分别对应乘M^2,乘M到M^2,不乘任何数。

一般为了方便,选择取M为(1<<15)=32768.缺点是空间消耗比较爆炸,在一些情况下精度也并不友好。

手写复数套装code:

 

OI之路很辛苦,转载请注明来自Newuser小站《【MOBAN】多项式算法模板和小记录》

评论