2023 笔记

Catalan 数

Catalan 数表示为 $C_n$，有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$，定义应该使用的是递推式。

常见的与 Catalan 数有关的问题：

$n$ 个结点的二叉树数量为 $C_n$。
从 $(0,0)$ 到 $(n,n)$ 的不穿过 $y=x$ 的非降路径数为 $2C_n$。
括号序列
出栈序列

很多问题可以为转化为第二个格路计数问题（3 和 4 就是如此）。

格路计数问题的证明：

很显然，$y=x$ 下方和上方的路径数都是 $C_n$，一共有 $2C_n$ 条合法路径，在这里我们只考虑路径在 $y=x$ 下方的情况。

首先，证明合法路径数满足 Catalan 数递推式。

一条合法路径一定与 $y=x$ 有不少于两个交点（$(0,0)(n,n)$ 就是两个交点），考虑除 $(n,n)$ 外的最后一个交点，假设为 $(t,t)$，那么从 $(0,0)$ 到 $(t,t)$ 就是一个规模为 $t$ 的子问题，答案为 $C_t$，而从 $(t,t)$ 到 $(n,n)$ 的部分不会再有与 $y=x$ 的交点（根据定义），所以可以被转化为从 $(t+1,t)$ 到 $(n,n-1)$，在 $y=x-1$ 下方的路径数，这是一个规模为 $n-t-1$ 的子问题，答案为 $C_{n-t-1}$。

于是，总答案为 $\sum_{t=0}^{n-1}C_tC_{n-t-1}$，与 Catalan 数递推式相同。

接下来，证明合法路径数满足 Catalan 数通项公式。

所有从 $(0,0)$ 到 $(n,n)$ 的路径数为 $\dbinom{2n}{n}$，考虑从中减去所有的不合法方案数。

对于一条穿越 $y=x$ 的路径，其一定与 $y=x+1$ 有交点，我们取最后一个交点，并将此后的路径关于 $y=x+1$ 对称，这样即可得到一条从 $(0,0)$ 到 $(n-1,n+1)$ 的路径。

从 $(0,0)$ 到 $(n-1,n+1)$ 的路径一定与 $y=x+1$ 有交点，可以证明，这些路径与从 $(0,0)$ 到 $(n,n)$ 的不合法路径构成双射。

于是，答案为 $\dbinom{2n}{n}-\dbinom{2n}{n+1}=\dbinom{2n}{n}-\dbinom{2n}{n}\cdot\dfrac{n}{n+1}=\dfrac{\binom{2n}{n}}{n+1}$。

这样就证明了格路计数问题的答案为 Catalan 数，同时证明了 Catalan 数的通项公式。

关于双连通分量的实现

有的人把双连通分量称作 e-DCC 和 v-DCC，我喜欢叫 BCC，缩写自 Biconnected Component。

点双有两种实现方式：

允许走树边，也就是 $u$ 可以走到 $fa_u$，这样 $low_u$ 最大也就是 $dfn_{fa_u}$（$low_v$ 最大是 $dfn_u$），此时判定当前点是割点或点双中深度最浅的点的条件是 $low_v=dfn_u$。
不允许走树边，此时判定条件是 $low_v\ge dfn_u$。

OI Wiki 使用第一种实现，我喜欢使用第二种。

边双注意根所在边双不会在正常 tarjan 过程中被处理，需要特判，点双则没有这个问题。

CF Blog 上的一道题

Link

给定正整数 $n$，考虑如何求 $\dfrac 1x+\dfrac 1y=\dfrac1n$ 的所有正整数解。

很显然，$x,y>n$，设 $x=n+a,y=n+b$，代入得：
$$
\begin{array}{c}
\dfrac1{n+a}+\dfrac1{n+b}=\dfrac1n\\
\dfrac{2n+a+b}{n^2+an+bn+ab}=\dfrac1n\\
ab=n^2
\end{array}
$$
于是计算 $n^2$ 的约数个数即可。

这个题可以出成 $n\le 10^{12}$，保证 $n$ 的约数个数为奇数，可以作个 T1，虽然感觉有点缝合。

鞅的停时定理

我也不是很懂这到底是个什么东西，但是你可以为一个随机过程的每个局面设计一个势能函数使得每次转移势能都期望 $-1$，那么我们可以直接计算初始状态与终止状态的势能差，从而得到期望步数。

注意我们要求终止状态的势能是唯一的，并且通常是最大值 / 最小值，否则，我们可能会对两个不同的状态计算出期望步数为 $0$ 甚至负数的反常情况。

至于更本质的理解，我也不懂，我猜测是违背了停时定理中 $t$ 几乎必然有限的条件。

色多项式

$G(V,E)$ 的色多项式 $P(G,k)$ 是一个表示图 $G$ 进行 $k$ 染色方案数的多项式。可以证明对于图 $G$ 进行 $k$ 染色的方案数是关于 $k$ 的多项式。

OI 中我认为比较常用的是这样一个公式：
$$
P(G,k)=P(G-e,k)-P(G\cdot e,k)
$$
其中，$G-e$ 表示从 $G$ 中去掉边 $e$，$G\cdot e$ 表示将 $e$ 的两个端点合并。

Update：这玩意也被称作 Deletion-Contraction Formula。

如果我们递归下去可以得到一个容斥公式：
$$
P(G,k)=\sum_{S\subseteq E}(-1)^{|S|}k^{c(G(S))}
$$
$c(G(S))$ 表示由 $S$ 中边构成的生成子图的连通块个数。本质上是在枚举有哪些边被合并，剩下的边就应当被删除。

这样我们就可以方便的计算特殊图的色多项式，以环为例，我们用 $C_n$ 表示 $n$ 个点的环。
$$
\begin{aligned}
P(C_n,k)&=\sum_{i=0}^{n-1}(-1)^i\binom ni k^{n-i}+(-1)^nk\\
&=\sum_{i=0}^{n}\binom ni (-1)^i k^{n-i}-(-1)^n+(-1)^nk\\
&=(k-1)^n+(-1)^n(k-1)
\end{aligned}
$$
非常强大。

闵可夫斯基和

闵可夫斯基和是对两个位置向量集合两两相加的结果：
$$
A+B=\{\mathbf a+\mathbf b\mid \mathbf a\in A,\mathbf b\in B\}
$$

可以证明，两个凸包的闵可夫斯基和仍然是一个凸包。

证明思路：证明凸包（凸多边形）的方法是，任取两个点，这两点连成的线段上任意一点都在凸包内。

$A,B$ 是两个凸包，$C=A+B$，考虑任取 $a,b\in C$，设 $a=c+d,b=e+f$，其中 $c,e\in A$，$d,f\in B$，实数 $t\in[0,1]$：
$$
\begin{aligned}
t\cdot a+(1-t)\cdot b&=t\cdot(c+d)+(1-t)\cdot (e+f)\\
&=t\cdot c+(1-t)\cdot e+t\cdot d+(1-t)\cdot f
\end{aligned}
$$
而很显然，$t\cdot c+(1-t)\cdot e \in A$，$t\cdot d+(1-t)\cdot f\in B$，于是命题得证。
我们可以将两个凸包的所有边按照斜率排序后拼接起来，然后直接得到闵可夫斯基和。

这个如果在纸上画一画是一个很显然的结论。

高维前缀和 / 差分

高维前缀和 / 差分的第二维循环顺序是不重要的，原因是每一维实际上是有两种取值。

二维平面上的变换

将初始向量表示为 $(x,y,1)$ 的形式，左乘在变换矩阵上。

平移

按照向量 $(x,y)$ 移动。
$$
\begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
x & y & 1
\end{pmatrix}
$$

旋转

绕原点旋转 $\theta$。
$$
\begin{pmatrix}
\cos \theta & \sin \theta & 0\\
-\sin \theta & \cos \theta & 0\\
0 & 0 & 1
\end{pmatrix}
$$

投影

在单位向量 $(x,y)$ 方向上的投影。
$$
\begin{pmatrix}
x^2 & xy & 0\\
xy & y^2 & 0\\
0 & 0 & 1
\end{pmatrix}
$$
推导方式。$\mathbf{v}$ 在 $\mathbf{w}$ 上的投影为 $\dfrac{\mathbf{v}\cdot\mathbf{w}}{|\mathbf{w}|}\cdot\mathbf{w}$，一次是点乘，一次是数乘。变换矩阵中我们要求 $|\mathbf{w}|=1$，式子可以更简洁一些。

翻转

关于单位向量 $(x,y)$ 翻转。
$$
\begin{pmatrix}
2x^2-1 & 2xy & 0\\
2xy & 2y^2-1 & 0\\
0 & 0 & 1
\end{pmatrix}
$$
考虑在投影的基础上进行变换。

同余最短路

同余最短路不一定要跑最短路。

由于最短路不会经过一个点两次，或者说由于基准物品的最优性，我们在新增一个物品的时候，可以绕着每个子环跑两圈完全背包，这样即可保证每个点转移到了环上其他的所有点。

Puzzle

The Puzzle TOAD #5

Description

有三桶水，每个桶中的水量均为一个正整数，每次可以将其中一桶水的一部分倒入另一个桶中，要求使另一个桶中的水量翻倍。

试说明：对于任意初始水量，我们都可以在有限次操作内清空某一个桶。

Solution

很清新的 puzzle，切入点找到了整道题也就迎刃而解。

首先来考虑只有两个桶的情况，那么我们每次只能将水从水多的桶倒入水少的桶，由于总状态数有限，不难发现我们最终一定会进入一个循环。这里需要注意到，如果两个数一偶一奇，不妨设为 $(a,b)$，那么从任意初始状态操作若干次后一定会回到自身，因为在这种情况下，每个状态都有唯一的前驱 $(a/2,b+a/2)\to (a,b)$，所以不可能出现一个环上再接入一条链的情况。于是我们可以通过若干次操作实现「在环上倒退一步」，从一奇一偶的状态走到其前驱。

接下来，对于奇偶偶的情况，如果有一个偶数是 $4$ 的倍数，则我们可以关于这个数和奇数做一次倒退操作，在不改变所有数奇偶性的情况下使奇数变大，否则，在两个偶数中操作一次就可以得到 $4$ 的倍数。由于奇数在不断变大，显然最终某个偶数一定会变成 $0$。

对于剩余情况，奇奇奇的情况可以通过任意操作转化为奇偶偶，偶偶偶可以将所有数同除二规约到规模更小的问题，奇奇偶可以在两个奇数中操作转化为偶偶偶。

感觉可以出成 IO 交互题，操作数应该是平方级别的。

高维差分

Link

$\Delta A(x)=A(x)-A(x+1)$.

To compute $\Delta^{d-1} A(0)$ and $\Delta^{d-1} A(1)$ in $O(d)$, one can use the binomial formula:
$$
\Delta^k A(x) = \sum\limits_{i=0}^k (-1)^i \binom{k}{i} A(x+i).
$$

Indeed, if we denote by $S$ an operator such that $S A(x) = A(x+1)$, then

$$
\Delta^k A(x)= (I-S)^k A(x)= \sum\limits_{i=0}^k (-1)^i \binom{k}{i} S^i A(x) = \sum\limits_{i=0}^k (-1)^i \binom{k}{i} A(x+i).
$$
高维前缀和的话其实可以转化为路径计数，但是我暂时不知道那玩意有没有系统一点的理论。

满足四边形不等式的序列划分问题中的答案凸性

原论文翻译 by Itst

简而言之，对于序列划分问题，只要代价函数满足四边形不等式，答案关于划分段数就是凸的。

这为答案凸性的寻找提供了十分有利的帮助，也为 Aliens、邮局加强版、忘情等一系列题目的答案凸性间接提供了证明。

事实上 wqs 二分、斜率优化、决策单调性这些 dp 优化技巧很多时候会一起出现，所以这一结论是非常强大的。

平均数与中位数的处理技巧

二分后，平均数可以考虑将所有数减去 $mid$，中位数可以考虑将所有 $\le mid$ 的数变成 $0/-1$，$> mid$ 的变成 $1$。

CF1486D Max Median / AGC006D Median Pyramid Hard

矩形面积交

这个东西和并不同。并可以看作 $(x\in X_1 \land y\in Y_1) \lor (x\in X_2 \land y\in Y_2)\lor \dots$，这里我们只能采用扫描线来解决这个问题；交则相当于把中间的 $\lor$ 也改为 $\land$，这样我们可以任意调换条件之间的顺序，事实上，我们可以将对横坐标的限制和对纵坐标的限制拆开，在两维上分别做线段覆盖，拓展到更高维度亦是如此。

自然数幂和与 popcount

令 $S_0, S_1$ 分别为 popcount 为偶数与奇数的自然数集合，则在 $k>p$ 时，我们有如下结论：
$$
\sum_{i\in [0,2^k)\cap S_0} i^p=\sum_{i\in [0,2^k)\cap S_1} i^p
$$
证明：我们将上面的式子记作 $(k, p)$，对 $k$ 进行归纳。

容易验证 $(1,0)$ 成立。接下来假设 $\forall p<k'<k$ 均有 $(k',p)$ 成立。

从原式中提取出 $2^{k-1}$。
$$
\sum_{i\in[0,2^{k-1})\cap S_0} i^p+\sum_{i\in[0,2^{k-1})\cap S_1} (i+2^{k-1})^p=\sum_{i\in[0,2^{k-1})\cap S_1} i^p+\sum_{i\in[0,2^{k-1})\cap S_0} (i+2^{k-1})^p
$$
二项式展开并移项：
$$
\begin{aligned}
\sum_{i\in[0,2^{k-1})\cap S_0} i^p - \sum_{i\in[0,2^{k-1})\cap S_1} i^p &= \sum_{i\in[0,2^{k-1})\cap S_0}\sum_{j=0}^p 2^{j(k-1)}i^{p-j} - \sum_{i\in[0,2^{k-1})\cap S_1}\sum_{j=0}^p 2^{j(k-1)}i^{p-j}\\
\sum_{i\in[0,2^{k-1})\cap S_0} i^p - \sum_{i\in[0,2^{k-1})\cap S_1} i^p &= \sum_{j=0}^p 2^{j(k-1)}\left(\sum_{i\in[0,2^{k-1})\cap S_0}i^{p-j} - \sum_{i\in[0,2^{k-1})\cap S_1}i^{p-j}\right)
\end{aligned}
$$
右边提取出 $j=0$ 的项可以和左边消去，原式化为：
$$
\sum_{j=1}^p 2^{j(k-1)}\left(\sum_{i\in[0,2^{k-1})\cap S_0}i^{p-j} - \sum_{i\in[0,2^{k-1})\cap S_1}i^{p-j}\right)=0
$$
$p=0$ 时，该式成立；$p>0$ 时，由于 $k-1>p-j$，由归纳假设，该式成立。

故原命题得证。

符号交替的二项式前缀和

求：
$$
\sum_{i=0}^n (-1)^i \binom ki
$$
考虑使用生成函数。首先有：
$$
(1-x)^k=\sum_{i=0}^k(-1)^i\binom ki x^i
$$
对其做前缀和则有：
$$
\frac 1{1-x}\cdot (1-x)^k=\sum_{i=0}^k\left(\sum_{j=0}^i(-1)^j \binom kj\right)x^i
$$
于是我们要求的式子即为：
$$
[x^n]\frac 1{1-x}\cdot (1-x)^k=[x^n](1-x)^{k-1}=(-1)^n\binom{k-1}n
$$
Also see: Truncated alternating binomial sum

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog