《浅谈杨氏矩阵在信息学竞赛中的应用 袁方舟》膜拜有感

前方高能，非战斗人员请撤离（都是很干的数学概念）

1. 前言

杨表 (Young tableaux)，又叫杨氏矩阵，是一个啥都能掺一脚的代数结构。

为了方便讨论，先来点定义。

杨图：令 $\lambda = (\lambda_1,\lambda_2,\ldots,\lambda_m)$ 满足 $\lambda_1\ge\lambda_2\ge\ldots\lambda_m\ge 1,n=\sum \lambda_i$。一个形状为 $\lambda$ 的杨图是一个表格，第 $i$ 行有 $\lambda_i$ 个方格，其坐标分别为 $(i,1)(i,2)\ldots(i,\lambda_i)$。下图为 $n=9,\lambda=(4,2,2,1)$ 的杨图。

$\left[\begin{array}{c} * & * & * & * \\ * & * \\ * & * \\ * \end{array}\right]$

半标准杨表：将杨图填上数字，满足每行数字单调不减，每列数字单调递增。

标准杨表：将 $1,2,\ldots,n$ 填入杨图，满足每行、每列数字单调递增。下图为 $n=9,\lambda=(4,2,2,1)$ 的一种标准杨表。

$\left[\begin{array}{c} 1 & 4 & 7 & 8 \\ 2 & 5 \\ 3 & 9 \\ 6 \end{array}\right]$

斜杨图：令 $\lambda = (\lambda_1,\lambda_2,\ldots,\lambda_m),\mu=(\mu_1,\mu_2,\ldots,\mu_{m'})$，则形状为 $\lambda/\mu$ 的斜杨图为杨图 $\lambda$ 中扣去杨图 $\mu$ 后剩下的部分。下图为 $(9, 7, 5, 1)/(5, 3, 2)$ 的斜杨图。

$\left[\begin{array}{c} \cdot & \cdot & \cdot & \cdot & \cdot & * & * & * & * \\ \cdot & \cdot & \cdot & * & * & * & * \\ \cdot & \cdot & * & * & * \\ * \end{array}\right]$

斜半标准杨表、斜标准杨表：猜都猜得到，不浪费时间了。

2. 杨表的插入操作 / RSK 算法

RSK 算法包括了插入和删除。删除操作其实就是插入反过来，不影响理解杨表就不写了。

想要插入 $x$ 时，从第一行开始，在当前行中找最小的比 $x$ 大的数字 $y$ (upperbound)（其实大于 $x$ 还是大于等于 $x$ 要看具体情况），交换 $x,y$，转到下一行继续操作；若所有数字比 $x$ 小则把 $x$ 放在该行末尾并退出（如果超出了杨图的行数，那么杨图行数加 $1$）

举个 $\alpha$ 粒子，将 $3$ 插入下图半标准杨表：

$\left[\begin{array}{c} 1 & 3 & 3 & 5 \\ 2 & 6 \\ 4 \end{array}\right] \begin{array}{c} \leftarrow 3 \\ \cdot \\ \cdot \end{array}$

第一行找到 $5$，变成：

$\left[\begin{array}{c} 1 & 3 & 3 & 3 \\ 2 & 6 \\ 4 \end{array}\right] \begin{array}{c} \cdot \\ \leftarrow 5 \\ \cdot \end{array}$

第二行找到 $6$，变成：

$\left[\begin{array}{c} 1 & 3 & 3 & 3 \\ 2 & 5 \\ 4 \end{array}\right] \begin{array}{c} \cdot \\ \cdot \\ \leftarrow 6 \end{array}$

第三行找不到比 $6$ 大的数字，放到末尾：

$\left[\begin{array}{c} 1 & 3 & 3 & 3 \\ 2 & 5 \\ 4 & 6 \end{array}\right]$

可以证明这样操作后仍然满足半标准杨表的定义。

上代码！

vector<int> a[N];
void insert(int x) {
    for (int i = 0;; i++) {
        auto it = upper_bound(a[i].begin(), a[i].end(), x);
        if (it == a[i].end()) {
            a[i].push_back(x);
            return;
        }
        swap(x, *it);
    }
}

3. 杨表与 LIS

LIS (Longest Increasing Subsequence) 就是广为人知的最长上升子序列（有时是不下降）。杨表之所以能和 LIS 有关，是因为杨表的插入操作，只看其中一行的话，正好是 dp 求 LIS 的算法。（虽然这是废话）

拓展一下，如果要求 $k$ 个不相交的 LIS，它们的长度之和最大为杨图前 $k$ 行长度之和，即 $\lambda_1+\lambda_2+\ldots+\lambda_k$。不过要注意，杨表前 $k$ 行并不能告诉我们 LIS 有哪些数。（类似 dp 求 LIS 后那个 dp 数组也无法告诉我们 LIS 有哪些数）

举个 $\alpha$ 粒子，如果把 $[1,5,3,2,6,7,4]$ 插入到杨表中得到：

$\left[\begin{array}{c} 1 & 2 & 4 & 7 \\ 3 & 6 \\ 5 \end{array}\right]$

显然 $1,2,4,7$ 不是 LIS，LIS 应该是 $1,5,6,7/1,3,6,7/1,2,6,7$。不过长度是相同的。

这题 (opens new window)就是求 k-LIS 的题了。但是 $k$ 没有限制，如果维护的杨表行数太大，朴素的插入算法 $O(n^2 \log n)$ 肯定过不了。这就需要一个杨表的性质：如果把比较运算反过来（大于变小于等于），插入操作后的杨图和原来的杨图是转置关系（但是杨表和杨表不是转置的，只是形状转置），具体可以看看这题的题解。

话说回来，由于杨表和转置杨表的关系，我们可以得出一个结论，如果杨表的第一行数字个数是最长上升子序列长度，那么第一列数字个数是最长不上升子序列长度。如果某题限制了最长上升子序列长为 $\alpha$，最长不上升子序列长为 $\beta$，我们就可以把它和行数为 $\alpha$，列数为 $\beta$ 的杨表联系起来。（现在还没用，一一对应的关系在下文会讲）

4. 杨表与排列

我们可以将排列的数字按顺序插入到空杨表中，这样就会得到一个标准杨表。但是这会出现两个排列对应一个杨表的情况，比如排列 $[2,1,3]$ 和排列 $[2,3,1]$ 都会得到杨表 $\left[\begin{array}{c}1 & 3 \\ 2 \end{array}\right]$，出大问题。

考虑一个排列对应两个杨表，每插入一个数字到杨表 $A$，我们在杨表 $B$ 对应位置记录这个数字的下标（下标从 $1$ 开始）。

可以证明 $B$ 也是个标准杨表。

举个 $\alpha$ 粒子，对于排列 $[2,3,1]$，插入 $2$ 得到：

$A=\left[\begin{array}{c}2 \end{array}\right], B=\left[\begin{array}{c}1 \end{array}\right]$

插入 $3$ 得到：

$A=\left[\begin{array}{c}2 & 3 \end{array}\right], B=\left[\begin{array}{c}1 & 2 \end{array}\right]$

插入 $1$ 得到：

$A=\left[\begin{array}{c}1 & 3 \\ 2 \end{array}\right], B=\left[\begin{array}{c}1 & 2 \\ 3 \end{array}\right]$

而 $[2,1,3]$ 会得到：

$A=\left[\begin{array}{c}1 & 3 \\ 2 \end{array}\right], B=\left[\begin{array}{c}1 & 3 \\ 2 \end{array}\right]$

这样，我们就把一个排列和两个标准杨表一一对应了起来。

5. 杨表和对合排列

对合排列是一种特殊的排列，把对合排列当成个置换后，自己乘自己等于单位置换。好理解一点就是 a[a[i]]=i。

比如 $\left[\begin{array}{c}1 & 2 & 3 \\ 2 & 1 & 3\end{array}\right]$ 就是个对合置换。

为什么要讲对合排列呢，因为把对合排列对应的两个标准杨表是相等的。这意味着一个对合置换和一个杨表是一一对应的关系。

6. 钩子公式

对于一个杨图 $\lambda$ 来说，一个方格的钩子 (hook) 函数等于它正右边方格数量 + 正下边方格数量 + 1，记为 $h_\lambda(x,y)$。

举个 $\alpha$ 粒子，杨图 $\lambda=(4,2,2,1)$ 中，$(1,1)$ 方格右边和下边各有 $3$ 个方格，加上自身总共 $7$ 个，即 $h_\lambda(1,1)=7$。另外还有 $f_\lambda(2,1)=4$，其他懒得写了。

$\left[\begin{array}{c} * & * & * & * \\ * & * \\ * & * \\ * \end{array}\right]$

给定杨图 $\lambda$，钩子公式可以告诉我们形状为 $\lambda$ 的标准杨表有多少个。钩子公式如下：

$f_{\lambda}=\dfrac{n!}{\prod h_{\lambda}(x)}$

很简单，就是 $n$ 的阶乘除以所有方格的钩子函数之积。为了写代码方便，钩子公式有第二个形式：

$f_{\lambda}=n!\dfrac{\prod_{1\le i<j\le m}(\lambda_i-i-\lambda_j+j)}{\prod_{i=1}^{m}(\lambda_i+m-i)!}$

基于这个公式，上代码！

int calc(vector<int> &a, int n) { // 阶乘 fact, 阶乘倒数 invfact 要自己写
    int m = a.size();
    long long ans = 1;
    for (int i = 0; i < m; i++)
        for (int j = i + 1; j < m; j++)
            (ans *= a[i] - i - a[j] + j) %= mod;
    for (int i = 0; i < m; i++)
        (ans *= invfact(a[i] + m - i - 1)) %= mod;
    (ans *= fact(n)) %= mod;
    (ans += mod) %= mod;
    return ans;
}

这题 (opens new window)结合了 LIS 和钩子公式（状压 dp 也可以，但是钩子公式更快）（注意排列和两个标准杨表对应，不要漏了平方），可以测测板子

但是但是但是，这个算法 $O(m^2)$ 的鸭，能不能再给力一点？

能。

把钩子公式改成 $f_\lambda=n!\dfrac{\prod_{1\le i<j\le m}(r_i-r_j)}{\prod r_i!},r_i=a_i+m-i$，考虑数组记录 $r_i$ 出现的次数，如果 $x$ 在 $r$ 中出现了记 $A[x]=1$，否则 $A[x]=0$（$x$ 肯定只出现一次），用 FFT 可以算出 $C[k]=\sum_{i-j=k} A[i]A[j]$，$\prod_{1\le i<j\le m}(r_i-r_j)$ 就等于 $\prod_{i=1}^{n} i^{C[i]}$

上代码！（只提供了 $\prod_{1\le i<j\le m}(r_i-r_j)$ 的计算）

const int nn = 1000010; // 比 n 大就行
long long A[N], B[N], r[N];
ll solve(ll a[], int m) {
    for (int i = 0; i < nn * 2; i++) A[i] = B[i] = 0;
    for (int i = 1; i <= m; i++) {
        r[i] = a[i] + m - i;
        A[r[i]] = 1;
        B[nn - r[i]] = 1;
    }
    long long ans = 1;
    ntt::conv(A, B, nn * 2, A);
    for (int i = 1; i < nn; i++)
        if (A[i + nn]) (ans *= qpow(i, A[i + nn])) %= mod;
    // 这里还要乘以 n! 除以 prod r[i]!
    return ans;
}

这题 (opens new window)就是带FFT的钩子公式的例题

---

以上，阳间的杨表已经介绍完毕了。

接下来是阴间的杨表。

7. 杨图的随机游走

这部分袁老师讲错了，我找了原论文但是没看懂（菜），最后还是靠猜。不过这部分没什么用就是了。

给定一个杨图，初始随机出现在杨图任一位置（每个位置概率 $\tfrac 1 n$），然后每次操作都可以往右走任意格或往下走任意格（每个位置概率 $\tfrac 1 {h_\lambda(x)}$），则走到边角 $(r,s)$ 概率为：

$\dfrac 1 n\prod_{i=1}^{r-1}\dfrac{h_\lambda(i,s)}{h_\lambda(i,s)-1}\prod_{j=1}^{s-1}\dfrac{h_\lambda(r,j)}{h_\lambda(r,j)-1}$

另外还有带权的版本，每行权重 $x_i$，每列权重 $y_j$，初始随机出现在杨图某一位置（概率权重 $x_iy_j$），向下走到某位置的概率权重为目标行的权重，向右为列的权重，则走到边角 $(r,s)$ 概率为：

$\dfrac{x_ry_s}{\sum x_iy_j}\prod_{i=1}^{r-1}\left(1+\dfrac{x_i}{\sum x_{i+1..r}+\sum y_{s+1..\lambda_i}}\right)\prod_{j=1}^{s-1}\left(1+\dfrac{y_j}{\sum x_{r+1..\lambda^T_j}+\sum y_{j+1..s}}\right)$

oh 这里概率权重指的是，进行某个操作的概率等于这个操作的概率权重除以所有可行的操作的概率权重。

写在这里就当给论文纠错吧。

8. 斜杨表和不相交网格路径

约定坐标系中 $x$ 轴正方向是右，$y$ 轴正方向是上。

网格中从整点 $S(x_0,y_0)$ 走到整点 $T(x_1,y_1)$，每次只能往右或上走一个单位，那么方案数为 $P(S,T)=\displaystyle\dbinom{x_1-x_0+y_1-y_0}{x_1-x_0}$。

一个斜半标准杨表 $\lambda/\mu$，每个数字值域 $[1,z]$，则 $\lambda/\mu$ 可以表示为 $m$ 条不相交路径 $(\mu_i-i,1)\rightarrow (\lambda_i-i,z),i=1\ldots m$。

这意味着，我们在斜半标准杨表与不相交网格路径之间建立了一一对应关系，套用 LGV 引理，斜半标准杨表的个数就可以写出来了：

$f'_{\lambda/\mu}=\det\left[\dbinom{\lambda_j-j-\mu_i+i+z-1}{\lambda_j-j-\mu_i+i}\right]_{i,j=1}^m$

如果要考虑斜标准杨表，这意味着要把 $\sum(\lambda_i-\mu_i)$ 个纵坐标分配给各个路径，一通我也看不懂的操作（好像是行列式的定义），得到：

$f_{\lambda/\mu}=(\sum_{i=1}^{m}(\lambda_i-\mu_i))!\det\left[\dfrac{1}{(\lambda_j-j-\mu_i+i)!}\right]_{i,j=1}^m$

注：$\dfrac{1}{a!}$ 在 $a<0$ 时等于 $0$。

代入 $\mu_i=0$ 可以得到标准杨表个数的另外一个公式，因为没钩子公式好用，就不放在这了。

斜杨表计数好像没题目可刷，难受。只能拿出论文里的题目了。

Euler numbers

长为 $2n$ 的排列中，计算满足 $a_1 < a_2 > a_3 < \ldots > a_{2n-1} < a_{2n}$ 的方案数。

恰好对应了 $(2n-1 + 2, 2n-2 + 2, \ldots , n + 2)/(2n-1, 2n-2, \ldots , n)$ 的斜标准杨表，就是长得像楼梯一样的形状。然后就用公式。

但是，这个欧拉数 A000364 是有 $O(n \log n)$ 算法的。具体咋搞论文好像没说。

（时隔多日我滚回来了，只要展开指数型生成函数 sec(x) 就行了。）

9. 半标准杨表与 k-Dyck Path

没错，喜闻乐见的一一对应关系又来了。这次出场的是会斜着走的 $k$ 个人，每个人都从 $(0,0)$ 走到 $(2n,0)$，只能在第一象限走，只能往右上和右下方向走，而且要求编号小的路径在编号大的路径上方。

看懂是不存在的，直接拿来主义。

列数不超过 $2k$ 的，元素都在 $[1, n]$ 内的且每行大小为偶数的半标准杨表和长度均为 $2n + 2$ 的 k-Dyck Path 形成双射关系，且计数公式如下：

$b_{n,k}=\prod_{1\le i\le j\le n}\dfrac{2k+i+j}{i+j}$

考虑下面的数严格大于上面的数，行数自然是有限的。

10. 半标准杨表与对称单调矩阵

我们考虑一个元素都在 $[1, n]$ 内，列数不超过 $k$ 的半标准杨表。它的个数被证明和 $n\times n$ 的元素在 $[0, k]$ 内的对称矩阵满足每行每列都非严格递增的数量相同。

$a_{n,k}=\prod_{1\le i\le j\le n}\dfrac{k+i+j-1}{i+j-1}$

好家伙袁老师也不会证。（并不）

11. 半标准杨表计数

$f'_\lambda=\prod_{i,j\in\lambda}\dfrac{n+j-i}{h_\lambda(i,j)}=\prod_{1\le i<j\le m}\dfrac{\lambda_i-i-\lambda_j+j}{j-i}$

这里袁老师用了对称多项式和交错多项式等操作来证明。oh 不管了。

12. 总结

论文有 28 页，我看了足足一个星期，看到后面更是不求甚解，抄个公式就走，最后几个公式甚至连验算都没验，实在是水平有限。

杨表确实是个精妙的结构，学了那么久，我也不敢说我学会了多少。不过至少还是有点成就感的。