多项式补完计划

退役前给自己看的,删了一些东西放出来了,有兴趣可以看看


FFT,NTT全世界都会了...

分治FFT

是一类思想。举个板子:

给出了g_{1,...,n-1},求f_{0,...,n-1}

f_i = \sum_{j=1}^i f_{i-j} g_j

计算f需要用到之前的f。所以考虑像CDQ一样的做,用 左半部分贡献右半部分。

对于右半边的点x,左边有贡献:

w_x = \sum_{i=l}^{mid} f_i g_{x - i}

这个东西可以FFT做出来。

多项式求逆

倍增求解。假设已经求出了模\lceil \frac{x}{2} \rceil的解f_0^{-1}(x)

f(x)f^{-1}(x) \equiv f(x)f_0^{-1}(x)\pmod {\lceil \frac{x}{2} \rceil}

f^{-1}(x) - f_0^{-1}(x) \equiv 0 \pmod {\lceil \frac{x}{2} \rceil}

平方,移项

f^{-1}(x) \equiv (2 - f(x)f_0^{-1}(x)) f_0^{-1}(x) \pmod {x^n}

O(nlogn)

多项式除法

已知次数为n,mF(x),G(x),求

F(x) = Q(x)G(x) + R(x)

我们考虑反转一个多项式的系数,可以发现就是

A_R(x) = x^n A(\frac{1}{x})

那么利用反转化简

x^n F(\frac{1}{x}) = x^{n-m} Q(\frac{1}{x}) x^mG(\frac{1}{x}) + x^{n-m+1} x^{m-1}R(\frac{1}{x})

F_R(x) \equiv Q_R(x)G_R(x) + x^{n-m+1}R_R(x) \pmod {x^{n-m+1}}

Q_R(x) \equiv F_R(x)G_R^{-1}(x)\pmod {x^{n-m+1}}

于是可以求解Q_R(x),然后求出Q(x),R(x)O(nlogn)

多项式求导与积分

f(x) = \sum_{i=0}^n a_ix^i

f^{'}(x) = \sum_{i=0}^{n-1}(i+1)a_{i+1}x^i

\int_{1}^n a_i x^i = \sum_{i=1}^{n+1}\frac{a_{i-1}x^i}{i}

多项式泰勒展开

g(x) = \sum_{i=0}^{+ \infty} \frac{f^{(i)} (x_0) }{i!} (x - x_0)^i

多项式牛顿迭代

g(f(x)) \equiv 0 \pmod{x^n}

已知g(x),求f(x)

一个神奇的东西。其实有了她多项式这些问题都可以随便做啦~。

倍增求解。假装已经求出了f_0(x),满足:

g(f_0(x)) \equiv 0 \pmod{ x^{\lceil \frac{n}{2} \rceil} }

那么在f_0(x)泰勒展开

\sum_{i=0}^{+ \infty} \frac{g^{(i)}(f_0(x))}{i!}(f(x)-f_0(x))^i \equiv 0 \pmod{x^n}

因为

\forall i \geq 2, (f(x) - f_0(x))^i \equiv 0 \pmod{x^n}

所以可以化简得到

g(f_0(x)) + g^{'} (f_0(x))(f(x) - f_0(x)) \equiv 0 \pmod{x^n}

f(x) \equiv f_0(x) - \frac{g(f_0(x))}{g^{'}(f_0(x))} \pmod{x^n}

多项式ln

定义多项式的对数函数为其与麦克劳林级数的复合,即

\ln (1 - F(x)) = - \sum_{i=1}^{\infty} \frac{F^{(i)}(x)}{i}

我们令F(x)=ln(x)

G(x)=F(A(x))

G^{'} (x) = F^{'} (A(x)) A^{'} (x) = \frac{A^{'} (x)}{A(x)}

求导求逆求积分。O(nlogn)

多项式exp

同样定义多项式的对数函数为其与麦克劳林级数的复合,即

\exp F(x) = \sum_{i=0}^{\infty} \frac{F^{(i)}(x)}{i!}

F(x) \equiv e^{A(x)} \pmod{x^n}

\ln F(x) \equiv A(x) \pmod{x^n}

\ln F(x) - A(x) \equiv 0 \pmod{x^n}

那么考虑令

G(F(x)) \equiv \ln F(x) - A(x) \pmod{x^n}

因为G(F(x)) \equiv 0,可以把A(x)看作常数项,于是很好求导

G^{'}(F(x)) \equiv \frac{1}{F(x)} \pmod{x^n}

用牛顿迭代可知

F(x) \equiv F_0(x)(1 - \ln F_0(x) + A(x)) \pmod {x^n}

O(nlogn)

多项式开根

会颓exp的式子之后,这个很naive。

F(x) \equiv \frac{A(x)}{2F_0(x)} + \frac{F_0(x)}{2} \pmod{x^n}

O(nlogn)

多项式快速幂

倍增可以,但是有点慢

A^k(x) \equiv \exp(k \ln A(x))

O(nlogn)

关于多点求值插值什么的:懒得学,盲猜省选NOI不会考,咕咕(FLAG)

任意模数NTT

直接用MTT。考虑把数字拆成xM+y,其中M是一个界限,取2^{15}-1

那么直接考虑FFT,需要9次。

主要问题是有一个优化技巧:一次FFT做两个DFT

具体来说就是P(x)=A(x)+iB(x),Q(x)=conj(P(x))

那么对PFFT之后,Q(x)=conj(P(j)),j = (lim-i) \mod lim

DFT(A) = \frac{P+Q}{2},DFT(B)=-i\frac{P-Q}{2}

对于MTT的DFT部分,直接套这个Trick就行了。那么可以得出来xy的四个积。

但是IDFT的时候,两个数都是实部虚部都不为0,好像有点问题的样子。。

其实这个问题很好解决(虽然想了很久。。):令F=A+Bi,其中A,B都是点值表示,因为两个多项式A,B的系数表示都是只有实部不为0,那么仔细想一想可以发现,直接把F做IDFT就可以还原出来A,B,一个在实部一个在虚部。可以理解为,因为它们都是只有一个部有数,分别放在实虚部分,它们是互不影响的。


迷惑斯特林数系列

第二类行

最简单的一个。。

n^m = \sum_{i=0}^m {m \brace i} \binom{n}{i} i!

可以发现,把\sum扩展到n也是没有问题的

n^m = \sum_{i=0}^n {m \brace i} \binom{n}{i} i!

{m \brace n} = \frac{1}{n!} \sum_{i=0}^n \binom{n}{i} (-1)^{n-i} i^m

化简一下就是卷积

O(nlogn)

第一类行

有一个貌似能归纳证明的式子

\sum_{i=0}^n{n \brack i}x^i = x^{\overline n}

那么倍增求就行了,手动玩一下二项式。O(nlogn)

第二类列

把列写成OEF,考虑递推式,可以整理得到

x^m(\prod_{i=1}^m (1-ix))^{-1}

那么分治NTT就行了,O(nlog^2n)

第一类列

考虑组合意义,n个数,由m个轮换组成。那么构造轮换EGF(因为有标号),再除掉排列数

{ n \brack m } = \frac{n!}{m!} [x^n](\sum_{i=1} (i-1)! \frac{x^i}{i!})^m

不是很懂非1的ln,倍增完事O(nlog^2n)


一类O(n^2)的多项式技巧:以exp为例,看这里https://baka.online/noi-online3%e4%bc%98%e7%a7%80%e5%ad%90%e5%ba%8f%e5%88%97-%e9%9b%86%e5%90%88%e5%b9%82%e7%ba%a7%e6%95%b0exp/

剩下的更简单,模仿一下就有了


奇怪的题目:

付公主的背包

付公主的背包

首先显然构造函数f_i(x) = \frac{1}{1 - x^{v_i}}卷起来就行了。但是这个复杂度很高。

考虑用加法代替乘法,求个\ln就可以了。这题的\ln有极好的性质:

G(x) = \ln F(x) = \ln \frac{1}{1 - x^v}

考虑求导求积分化简式子:

G^{'}(x) = \frac{F^{'}(x)}{F(x)} = \sum_{i=1}^{\infty} v x^{xi - 1}

G(x) = \sum_{i=1}^{\infty} \frac{1}{i} x^{vi}

记录每种v有几个,暴力求系数,调和级数的复杂度,再敲个多项式\exp就行了。

发表评论

电子邮件地址不会被公开。必填项已用 * 标注