卡特兰数

卡特兰数表示有多少个序列由 $n$ 个 $1$ 和 $n$ 个 $-1$ 构成，且前缀和非负。
卡特兰数的第 $n$ 项等于 $\frac{\binom{2n}{n}}{n+1}$。

证明 1

Raney 引理

如果 $a_1,a_2,\dots,a_n$ 是任何一个和为 $1$ 的整数数列，则其所有循环位移中恰好有一个满足所有的前缀和都是正数。

证明：
考虑前缀和 $\{s_1,\dots,s_n\}$。假设 $x$ 是一个合法的开头。
那么对于 $i<x$，以 $x$ 开头，$i$ 结尾的区间和是 $1-s_{x-1}+s_i$。
对于 $i\ge x$， $x$ 开头，$i$ 结尾的区间和是 $s_i-s_{x-1}$。
由于 $x$ 是一个合法的开头，所以 $\forall i<x,s_i\ge s_{x-1}$，$\forall i\ge x,s_i>s_{x-1}$。
不难发现，满足条件的 $x$ 等价于 $s_{x-1}$ 是前缀和里最靠后的最小值。
当然，如果此时 $x-1=n$，那么合法的开头就是 $1$。

不难发现，卡特兰数等价于：$n+1$ 个 $1$ 和 $n$ 个 $-1$ 构成的，且前缀和严格大于 $0$ 的序列个数。
具体来说，就是在原来条件的基础上，在序列开头加上一个 $1$。

那么根据 Raney 引理，我们就只要求由 $n+1$ 个 $1$ 和 $n$ 个 $-1$ 构成的序列中有多少种循环同构等价类。
很明显就是 $\frac{\binom{2n+1}{n}}{2n+1}=\frac{\binom{2n}{n}}{n+1}$。

证明 2

直接考虑将 $+1$，$-1$ 看作折线，且折线不能碰到 $y=-1$ 这条直线。
不难发现，将一条路径从第一次触碰到 $y=-1$ 以后沿着 $y=-1$ 翻转，可以把一种不合法的方案一一对应到：从 $(0,0)$ 走到 $(2n,-2)$ 的方案数。
所以合法的方案数就是 $\binom{2n}{n}-\binom{2n}{n+1}=\frac{\binom{2n}{n}}{n+1}$。

题目描述

• 在一个 $1$ 行 $n$ 列的棋盘上，有 $m$ 个棋子，第 $i$ 个棋子在从左往右第 $pos_i$ 列，颜色是 $col_i$。
• 现在 Alice 和 Bob 要轮流操作，操作如下：
  • 选中一个棋子以及它到右边下一个同色棋子（若不存在则到底）之间的所有棋子（包含左边不包含右边）。
  • 全部向前移动同一个距离，移动之后要保证棋子没有重叠并且棋子之间相对位置不变。
• Alice 先手，谁不能动谁就输了。

解题思路

先考虑只有一种棋子，那么每次就只移动一枚棋子。
那么我们把棋子之间的空位看成石子，那么题目就可以转化为：

• 有 $k$ 堆石子，Alice 和 Bob 轮流操作，每次可以选定一堆不是最右边的石子，取出若干石子，移动到右边相邻的堆里。
• Alice 先手，谁不能动谁就输了。

那么这就是阶梯 NIM 的模板题了，可以参考 P3480 [POI2009]KAM-Pebbles。
这里来粗略的讲一下阶梯 NIM 的做法。
为了方便起见，我们把顺序换一下，改成从第 $i$ 堆移动到第 $i-1$ 堆，移到第一堆结束。
正常的 NIM 是直接把石子扔掉，然而在阶梯 NIM 中，我们可以把奇数堆看成垃圾桶。

• 如果有人把偶数堆放到奇数堆，那么就相当于把石子扔掉了。
• 如果有人把奇数堆放到偶数堆，必胜者为了保持自己的必胜状态，一定可以把这些石子重新移到奇数堆里（第一堆是奇数堆）。

所以阶梯 NIM 就相当于只有偶数堆的普通 NIM，那么他的 SG 值就是偶数堆个数异或起来。

Lucas 定理

形式：
对于质数 $p$，和非负整数 $n$，$m$，有：
令：$n=(\overline{a_{k-1}a_{k-2}\dots a_2a_1})_p$，表示 $n$ 在 $p$ 进制下的形式。
令：$m=(\overline{b_{k-1}b_{k-2}\dots b_2b_1})_p$，表示 $n$ 在 $p$ 进制下的形式。
那么有：

$$\binom{n}{m}\equiv\prod^{k-1}_{i=0}\binom{a_i}{b_i}\pmod p$$

证明

引理

对于多项式 $F(x)$，有 $F(x)^p=F(x^p)$。

证明：
根据数学归纳法，只要证明: $(F(x)+G(x))^p=F(x)^p+G(x)^p$ 即可。
通过二项式定理，有：

$$(F(x)+G(x))^p=\sum_{i=0}^{p}{\binom{p}{i}F(x)^iG(x)^{p-i}}$$

只要再证明 $\forall 1\le x<p$，都满足 $p\mid\binom{p}{x}$ 即可。
显然：

$$\binom p x=\frac{p!}{x!(p-x)!}$$

又因为 $p$ 是质数且 $1\le x<p$ ，所以分子包含质因子 $p$，而分母不包含，因此 $p\mid\binom{p}{x}$。

先定义多项式 $F(x)=(1+x)^n\bmod p$，那么 $\binom{n}{m}\bmod p$ 就是 $x^m$ 项的系数。

$$\begin{aligned} F(x)&\equiv(1+x)^n&\pmod p\\ &\equiv\prod_{i=0}^{k-1}(1+x)^{a_ip^i}&\pmod p\\ &\equiv\prod_{i=0}^{k-1}(1+x^{p^i})^{a_i}&\pmod p\\ &\equiv\prod_{i=0}^{k-1}(\sum_{j=0}^{a_i}\binom{a_i}{j}x^{jp^i})&\pmod p\\ \end{aligned}$$

那么显然 $x^m$ 的系数就是 $\prod^{k-1}_{i=0}\binom{a_i}{b_i}\bmod p$，因为对于这 $k-1$ 项中，每一项都只能选择 $\binom{a_i}{b_i}x^{b_ip^i}$。

前置芝士

1. 费马小定理

内容

对于任意质数 $p$ 和 $a$，其中 $p\nmid a$，满足：

$$a^{p-1}\equiv 1\pmod p$$

证明

根据裴蜀定理，可以知道 $\{1\dots n\}$ 与 $\{a\dots(an)\}$ 是一一对应的，因此：

$$\begin{aligned} \prod_{i=1}^{p-1}ia&\equiv\prod_{i=1}^{p-1}i&\pmod p\\ a^{p-1}\prod_{i=1}^{p-1}i&\equiv\prod_{i=1}^{p-1}i&\pmod p\\ a^{p-1}&\equiv1&\pmod p \end{aligned}$$

杂谈

最近在 zhihu 看到很多人试图和葛立恒数比大小，我就也想了想。

我想到了一个比较大的数，但是感觉肯定比葛立恒数小，但感觉挺有意思的，就分享一下。

不知道有没有人会证明。

先定义：

$$\begin{cases} f^{1}(x)=f(x) \\ f^{a}(x)=f(f^{a-1}(x))&x\ge2 \end{cases}$$

然后定义：

$$\begin{cases} g_{1}(x)=x^x \\ g_{a}(x)=g^{g_{a-1}(x)}(g_{a-1}(x)) \end{cases}$$

这道题直接 $\operatorname{mod} \varphi(p)$ 的题解很多都是错的并且没有给出证明。

解题思路

首先这道题等价于求 $(A^{m-1}B)^{n-1}A^{m-1}$。

可以直接用高精度的矩阵快速幂，但是这里不讲。

不难发现在计算过程中矩阵一定是 $\begin{bmatrix}a&b\\0&1\end{bmatrix}$ 的形式。

所以现在问题转化为了计算型为 $A=\begin{bmatrix}a&b\\0&1\end{bmatrix}$ 的矩阵快速幂。

Part1

考虑讲矩阵对角化，也就是找到一个矩阵 $P$ 满足 $PAP^{-1}=B$ 是一个对角矩阵，也就是说:

题目大意

给定 $n$，$l$，$r$ 三个数，你需要和交互器博弈。

有一个长度为 $n$ 的区间，你和交互器轮流操作。

每次操作，操作的一方选择一个没有被染黑并且长度在 $l$ 和 $r$ 之间的区间，把它染黑。

无法操作的一方寄了，另一方获胜。

每次你操作要输出两个数 $a$ 和 $b$，表示你选择了区间 $[a,a+b-1]$。

每次交互器操作会给你两个数 $a$ 和 $b$，表示交互器选择了 $[a,a+b-1]$，若 $a=b=0$ 则表示你获胜，如果 $a=b=-1$ 则表示你寄了。

解题思路

只能说这题太妙了，场上 tourist 都没过。

题目描述

• 给定一个长度为 $n$ 的序列 $a_1,a_2\dots,a_n$。
• 对于 $1\le i\le j\le n$，你可以花费 $(i-j)^2\cdot\operatorname{min}(a_i,a_{i+1}\dots a_j)$ 的代价从 $i$ 跳到 $j$。
• 你现在要对于所有的 $1\le k\le n$，输出从 $1$ 到 $k$ 的最段路。
• $1\le a_i\le n\le4\times10^5$。

解题思路

首先考虑 $O(n^2)$ 的 DP，$f_i$ 表示从 $1$ 到 $i$ 的最短路径，转移很简单。

现在要考虑把这个 DP 优化到可以接受的时间复杂度内，考虑有以下性质。

性质1

对于 $1\le i\le j\le n$，如果直接从 $i$ 跳到 $j$，那么一定不会比经过区间最小值 $a_k$ 跳两次更优。