当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

分类 算法 下的文章

ZJOI 2019 了,机房同学也差不多都会基本多项式了,就写篇有关简单的多项式操作复习笔记吧 QAQ

约定:以下操作默认 n = \deg(F(x)) + 1 ,等号一般表示在 \bmod\ {x^n} 的意义下同余。

多项式乘法

可以先把多项式的系数转为点值,各位分别乘起来以后再插值出原多项式。考虑到单位根 / 原根的性质,我们有 FFT / NTT 。

READ MORE

写于:2019-01-13 20:44

更新于:2019-03-16 11:45

二项式反演:

\begin{aligned} f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i \\ f_n=\sum_{i=0}^{n}{n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}

READ MORE

定义:给定两个 n 次多项式 F(x)G(x) ,若对于任意多项式 P(x) 都有 G(F(P)) = P 则称 G(x)F(x) 的复合逆在模 x^n 意义下的复合逆。可以证明,若两个多项式常数项为 0 且一次项不为 0 则复合逆唯一且满足 F(G(x)) = G(F(x)) = x

遗憾的是,多项式复合逆没有 o(n \log n) 的做法,但我们可以以 O(n \log n) 的复杂度求出某一项,或者 O(n^2) 的复杂度求出所有项。

拉格朗日反演即

[x^n]F(x) = \frac 1n [x^{-1}] \frac 1 {G^n(x)}

可以证明

[x^n]F(x) = \frac 1n [x^{n-1}] (\frac x {G(x)})^n

后者可以直接快速幂(两只 \log),或者转换为 \ln\exp ,可以参考 关于求多项式 k 次幂的一些思考

如果需要证明可以参考 zjt 大爷的博客 (我是不会)。

READ MORE

Burnside 引理

ans = { 1 \over |G| } \sum_{f \in G} C(f) ,其中 C(f) 表示置换 f 中不动点的个数

Polya 定理

定义 L(f) 为置换 f 的循环节数,可以理解为对于任意一种状态至多经过 L(f) 次置换 f 可以变回原样。

易证置换 f 的不动点一定满足其自身的循环节为 L(f) ,即 C(f) = k^{L(f)} ,其中 k 表示颜色种数。

Polya 定理的公式即 ans = { 1 \over |G| } \sum_{f \in G} k^{L(f)}

READ MORE