• 反演魔术:反演原理及二项式反演

    首先我来说说什么是反演(inversion),对于一个数列$\{f_n\}$来说,如果我们知道另外一个数列$\{g_n\}$,满足如下条件 \[ g_n = \sum_{i=0}^n a_{ni}f_i \] 反演过程就是利用 $g_0, g_1, \cdots, g_n$ 来表示出 $f_n$ \[ f_n = \sum_{i = 0}^n b_{ni}g_i \] 本质上来说,反演其实是一个解线性方程组的过程,但是你观察后发现,这个矩阵实际上是一个三角矩阵,那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢?我们现在就来探讨一番! 我们首先讨论一下在什么情况下能够比较容易建立反演公式,之后介绍二项式反演以及它的两个应用,其中一个是错位排列问题

  • Catalan 数列及其应用

    卡特兰数(Catalan number)是组合数学中一个重要的计数数列,在很多看似毫不相关地方都能见到它的身影

    这篇文章介绍卡特兰数的几个应用以及它的推导过程,从组合推理和生成函数两个方面来推导出 Catalan 数的公式

    带限制条件的路径总数

    首先我们来看一个问题:

    在一个平面直角坐标系中,只能往右或往上走一个单位长度,问有多少种不同的路径可以从左下角 $(1, 1)$ 走到右上角 $(n, n)$,并且要求路径不能经过直线 $y = x$ 上方的点,下图中的路径都是合法的(图片来源 Wikipedia)

    如果没有限制条件,那么从左下角走到右上角一共有 $2n$ 步,有 $n$ 步是往右,另外 $n$ 步是往上,那么路径方案数就是 $2n$ 步中选择 $n$ 步往右,一共有 ${2n} \choose {n}$ (即 $C_{2n}^n$)种方案

    那么我们考虑一下这里面有多少种方案是不合法的

    首先对于每一种不合法的方案,它的路径一定与 $y = x + 1$ 有交。我们找到它与 $y = x + 1$ 的第一个交点,然后将这个点后面部分的路径关于 $y = x + 1$ 做一个对称。由于原来路径到达 $(n, n)$,新的对称之后的路径就会到达 $(n - 1, n + 1)$。这样我们把每一种不合法方案都对应到了一条从 $(1, 1)$ 到 $(n - 1, n + 1)$ 的路径,现在再来看是否每一条这样的路径都能对应到一种不合法方案,如果是,那么这就建立了一个一一映射的关系,也就是它们的方案总数相同。这是肯定的,因为每一条这样的路径必定与 $y = x + 1$ 有交,那么对称回去,就得到一条不合法方案

    由于从 $(1, 1)$ 到 $(n - 1, n + 1)$ 的路径有 ${n - 1 + n + 1} \choose {n - 1}$ 条,那么合法的方案就是

    \[C_n = { {2n} \choose {n} } - { {2n} \choose {n - 1} } = \frac{1}{n + 1} { {2n} \choose {n} }\]

    我们把这个方案数记为 $C_n$,这就是著名的 Catalan 数

  • Codeforces 上的一些组合计数问题

    Codeforces 15E. Triangles

    Problem:给出一个有规律的金字塔(如图),黑色的边是可以走路径,要求求出包含 $H$ 点的简单回路(不经过一个顶点两次)的条数,并且这个回路围住的部分不可以包含灰色的三角形,答案对 $10^9+9$ 取模,其中 $n \leq 10^6$,并且一定是一个偶数

    Example:当 $n = 2$ 时,一共有 $10$ 种方案,其中 $5$ 种是这样,另外的是顺时针顺序地走

    Solution:首先第 $1$ 层是最特殊的,因为这里没有灰色的三角形,然后注意到灰色的部分把整个金字塔分成了左部和右部

    路径现在可以分成三个部分

    • 在第一层移动,这一共 $10$ 种(见样例)
    • 进入左部或右部后直接回到 $H$
    • 进入左部(右部)后经过 $E$ 点进入右部(左部)

    对于第二种情况,在第一层的部分走法可以是(只有逆时针部分,实际上有 $8$ 种)

    • $A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow C \rightarrow A$
    • $A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow F \rightarrow C \rightarrow A$
    • $A \rightarrow B \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A$
    • $A \rightarrow B \rightarrow D \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A$

    对于第三种情况,在第一层(原来图中的两层现在算一层,也就是下面的 $n$ 是题目中 $n$ 的 $\frac{1}{2}$)的部分走法有 $2$ 种,左部到右部和右部到左部

    现在要统计的就是在左部和右部内有多少种方案,因为左部右部对称,所以答案是一样的,我们来考虑左部

    用 $S_n$ 表示在有 $n$ 层的金字塔中,走左部的方案数,因为走进左部后每一层都会遇到凹进去的部分,这部分只要枚举一下走了多远可以统计出第 $n$ 层一共有 $2\sum_{i=1}^{n-2} 2^i + 1 = 2^n - 3$ 这么多的情况

    然后要走到第 $n$ 层后就是 $\prod_{i=2}^{n} (2^i - 3)$ 种情况,然后走回去的路径有 $4$ 种选择,因此

    \[ S_n = \sum_{i=2}^{n} 4\prod_{j=2}^i (2^j - 3) \]

    答案是 $2S_n^2 + 8S_n + 10$

  • 牛顿迭代法在多项式运算的应用

    总算是快把 FFT 和生成函数的各种东西补了好多,膜拜策爷的论文和 Picks 的博客!

    这篇文章大概就是说如何用牛顿迭代法来解满足 $G(F(z)) \equiv 0 \pmod {z^n}$ 的 $F(z)$

    然后这东西可以比较方便地计算 $\sqrt{A(z)}$、$e^{A(z)}$,也就是多项式开根、求指数对数之类鬼畜的东西,在生成函数计数中十分有用

    顺便一提,这里说的“多项式”实际上你可以直接理解为生成函数或者形式幂级数

  • 平面图转对偶图及点定位

    平面图(planar graph)就是一个可以在平面上画出来的图,并且所有的边只在顶点处相交。平面图的对偶图(dual graph)是将这个平面的每个区域看成点,原图每一条边所属的两个相邻的区域对应在对偶图中的点有连边

    比如下面这张图(来源于 Wikipedia)

    蓝色的部分就是一个平面图,红色的就是它的对偶图

    平面图的点定位(point location)就是找出一个点属于这个图的哪个区域

    这篇文章介绍如何将一个平面图转换为其对偶图,和基于扫描线的离线的点定位算法

  • BZOJ-3456. 城市规划

    题目要求求出有 $n (n \leq 130000)$ 个点的有标号简单连通无向图的个数,答案 $\bmod 1004535809$ $(479 \times 2^{21} + 1)$,是个质数

    比如三个点的情况

    题目链接:BZOJ-3456

  • 多项式的多点求值与快速插值

    多项式的多点求值(multi-point evaluation)是给出一个多项式 $A(x)$,和 $n$ 个点 $x_0, x_1, \cdots, x_{n-1}$,要求求出 $A(x_0), A(x_1), \cdots, A(x_{n-1})$

    相反的,多项式的插值(interpolation)是给出 $n+1$ 个点 $(x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n)$,求出一个 $n$ 次多项式,使得这些点都在这个多项式上

    这两个问题实际上是在多项式的点值表示(point-value representation)和系数表示(coefficient representation)之间转换的方法,在快速傅里叶变换中由于带入值的特殊性质,可以在 $\mathcal O(n\log n)$ 的之间内将两种东西互相转换,但是,如果是任意给定点要求求值或者插值,就没有比较好的性质可以利用,但是仍然有比较快速的方法来计算它们