上一篇博文 中,介绍过数论中的 Mobius 反演公式,让我想起了另一个经典的反演公式:二项式反演公式。本质上反演公式就是矩阵求逆的过程。

只是它的逆有很简单的形式,因此才有了二项式反演公式,这个公式帮助我们队伍在 2014 年 ACM-ICPC 亚洲区域赛西安站拿银,当时 F 题答案直接算需要 $O(n^3)$ 复杂度,而利用二项式反演公式后,可以在 $O(n^2)$ 复杂度内完美解决。1A 过题,感觉超爽。

最后简单提一下:Mobius 反演公式及其矩阵形式

反演公式与其矩阵形式

其中 $g(n)$ 已知,解出 $f(n)$

为其反演公式,也称上面两式互为反演公式。

则上述反演公式本质上就是求矩阵 $A$ 的逆 $B$.

二项式反演公式

其中 $s \geq 0$ 则

Proof: 要证明反演公式,只需证明,对应的矩阵 $A$ 和 $B$ 互为逆即可. 令 $C = A \star B$ 则

证毕。

二项式反演写成卷积形式便于 NFT

不妨取 $s = 0$

等价于

也就是说二项式反演公式本质上是说:$\frac{1}{n!}$ 和 $\frac{(-1)^n}{n!}$ 互为卷积逆。

二项式反演公式的应用

二项式反演公式在组合数学和数论中都有诸多应用,这里简单的提两个。

(错排问题) 在 $n$ 个数字 $1, 2, \dots, n$ 形成 $n!$ 个排列 $a_1a_2 \dots a_n$ 中满足 $a_i \neq i$ 的排列有多少个

不妨设答案为 $D_n$ ,则可以看出恰好有 $r$ 个 $a_i=i$的排列数为 $\left(\begin{matrix} n \\ r\end{matrix}\right) D_{n-r}$,因此

因此

当然 $D_n$ 还有递推关系式 $D_1=0,D_2 = 1$

(满射个数) 求 $m$ 元集 $A$ 到 $n$ 元集 $B$ 的满身的个数 $g(m,n)$

类似于错排的思路,我们有

于是

Mobius 反演公式及其矩阵形式

由 Mobius 反演公式对应的矩阵我们有,若

则,其逆矩阵为

本文参考了豆瓣百度文库以及 许胤龙,孙淑玲《组合数学引论》。

单位根反演

DFT 的本质就是单位根反演

一个应用的例子

单位根反演转自:https://www.cnblogs.com/cjyyb/p/10838495.html

具体的例子求:$\sum_{i \in [0,n],k \mid i} \binom{n}{i} G^i$

计$f(x) = (G+x)^n$,则由上面公式

即复杂度 $O(k \log n)$,如果要结果模一个 NFT friendly 的,那就更好了!