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

首先我来说说什么是反演(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

本质上来说,反演其实是一个解线性方程组的过程,但是你观察后发现,这个矩阵实际上是一个三角矩阵,那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢?我们现在就来探讨一番!

我们首先讨论一下在什么情况下能够比较容易建立反演公式,之后介绍二项式反演以及它的两个应用,其中一个是错位排列问题

(more…)

Read More

Vim代码自动补全的神器:YouCompleteMe

YouCompleteMe 是一款非常强大的代码自动补全插件。我原先用的是 clang-complete,然后在最近有好几个月没有写东西了,系统一直更新更新到后面 clang-complete 出了一些问题,于是就开始找有什么其它的自动补全插件,然后就听说了 YouCompleteMe 的大名,如果想有比较详细的了解,可以参考它的官方文档,我在这里只是介绍一部分内容以及如何安装。

首先我们来看一段它的演示,你马上就会了解到这是有多强大了!

cpp-demo-of-youcompleteme

(more…)

Read More

特殊多项式在整点上的线性插值方法

首先我来解释一下题目是什么东西,假如给你一个 k 次多项式 P(x),并且已知了 P(0), P(1), \cdots, P(k),要求计算出 P(n), n \in \mathbb N 的值,由于已经知道了 k + 1 个点值,那么要插值出系数是可以在 \mathcal O(k^2) 完成,如果使用 FFT 的话是可以在 \mathcal O(k \log^3 k) 的时间内完成的[1],但是对于这个特别的问题,我们有一个 \mathcal O(k) 的算法!这好像是杜教先提出来的,然后还有这篇文章

(more…)

Read More

Catalan 数列及其应用

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

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

带限制条件的路径总数

首先我们来看一个问题:

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

450px-Catalan_number_4x4_grid_example.svg

如果没有限制条件,那么从左下角走到右上角一共有 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 数

(more…)

Read More

Codeforces 上的一些组合计数问题

Codeforces 15E. Triangles

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

5945210be972aa5fe947f3b8a3a0378a4cade844

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

5E-triangles

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

5E-triangles-level1

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

  • 在第一层移动,这一共 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 (more…)

Read More

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

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

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

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

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

(more…)

Read More

平面图转对偶图及点定位

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

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

300px-Duals_graphs.svg

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

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

这篇文章介绍如何将一个平面图转换为其对偶图,和基于扫描线的离线的点定位算法(对着代码看了一天终于会了QAQ)

(more…)

Read More

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

多项式的多点求值(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) 的之间内将两种东西互相转换,但是,如果是任意给定点要求求值或者插值,就没有比较好的性质可以利用,但是仍然有比较快速的方法来计算它们

(more…)

Read More