暂时只更了 多项式求逆 ,多项式 Ln ,多项式 exp。。
多项式求逆
众所周知,一个多项式求逆后是一个无穷次项的玩意。但是我们一般只需要它的前 n 项。
我们需要算出:
A×B≡1(modxn)这东西怎么做?背板 我们可以考虑倍增来求解。
首先如果 A 仅有一项,那么 B[0] 就是 A[0] 的逆元。
否则,假设我们已经有了
A×B′≡1(modx⌈n2⌉)同时我们必然有真正的 B 在模 x⌊n2⌋ 的时候也是 1 ,也就是说有
A×B≡1(modx⌈n2⌉)那么考虑两个式子相减
A×(B−B′)≡0(modx⌈n2⌉)由于 A 显然不同余于 0 ,所以有
B−B′≡0(modx⌈n2⌉)所以我们可以平方一下,把模的位置翻倍,并且由于是向上取整,我们知道前 n 项都会是 0。
(B−B′)2≡0(modxn)B2−2BB′+B′2≡0(modxn)然后我们可以给式子的一遍乘上一个 A ,仍然前 n 项是 0 :
A(B2−2BB′+B′2)≡0(modxn)由于 AB 显然是 1 ,所以我们拆开有
B−2B′+AB′2≡0(modxn)所以移项后有
B≡2B′−AB′2(modxn)B≡B′(2−AB′)(modxn)这个东西复杂度用主定理分析出来是 O(nlogn) 而不是 O(nlog2n) 哦。
同时也正好复习一下 NTT 的板子。等会顺便也复习下 分治 NTT 吧 QwQ
求逆跑得好快啊
cpp
1 |
|
多项式 Ln
我们考虑
B=lnA两边导一下:
B′=1AA′所以我们可以对 A 求逆乘上 A′ 然后再做个积分就完事了。
cpp
1 |
|
多项式 exp
已知 B(x)≡expA(x)(modxn) ,给定 A(x) 求出 B(x)。
首先考虑构造 G(x) ,满足 G(B(x))=0 ,那么
G(B(x))=lnB(x)−A(x)我们知道
G′(B(x))=1B(x)那么带入泰勒展开那里的公式
Bt+1(x)=Bt(x)−G(Bt(x))G′(Bt(x))(modx2t+1)=Bt(x)−lnBt(x)−A(x)1Bt(x)(modx2t+1)=Bt(x)−Bt(x)(lnBt(x)−A(x))(modx2t+1)=Bt(x)[1−lnBt(x)+A(x)](modx2t+1)实现上,我们可以先递归下去算出 B′(x)≡A(x)(mod⌈n2⌉) ,然后通过上面那个式子把它变成 B(x)(modxn) 。
复杂度也可以分析得 O(nlogn) 但是常数很大。(虽然据说论文哥可以让它跑得比我写的 NTT 还快)
cpp
1 |
|