杨氏矩阵（杨表）

[[ slider_text ]]

[[ item.c ]]

杨氏矩阵（杨表）

发布时间 2024-11-15 作者：秋千月 来源：算法小站

dp dp计数 杨表

## 杨氏矩阵
杨氏矩阵在处理 LIS（最长上升子序列）和 LDS（最长下降子序列）问题中很有用，同时它还有一些性质

### 杨氏矩阵定义
关于$$(n_1,n_2, \cdots, n_m)$$的杨表，是$$n_1+n_2 +\cdots + n_m$$个**不同整数**排列成若干行组成的阵列
第$$i$$行有$$n_i$$个元素，行之间保持左对齐，另外还必须满足
**每一行从左到右递增，每一列从上到下递增**

#### 对合
对合是一种**排列**，要求其逆排列与原排列相同
换句话说，排列只能进行**对换操作**，也就是说，对合中**要么只有长度为$$2$$的环**
要么就是单独的一个数

由此，可知对合的方案数是$$dp(n) = dp(n-1) + (n-1)dp(n-2)$$，其中$$dp_0 = dp_1 = 1$$
很好理解，要么是单独的一个数，要么是从$$n-1$$个数任选一个配对，剩下$$n-2$$个数形成方案

### 杨氏矩阵的插入和删除
![](/media/content_img/ins-young.png)
![](/media/content_img/ins-young2.png)

**插入算法**
定义$$S \leftarrow x$$表示$$x$$从第一行插入杨表中，定义$$x \rightarrow S$$表示从第一列插入
插入算法**默认总是把元素插入第一行**

1）在当前行找到**第一个大于$$x$$的数$$y$$**
2）没找到？将$$x$$放在该行末尾，放的位置记为$$(s, t)$$
特别地，第一次插入就没找到，放在第一行末尾，此时位置是$$(1, t)$$
3）如果找到了，那么就用$$x$$去替换$$y$$，然后移动到下一行，令$$x = y$$
重复操作1

**碰撞操作**
考虑到最终图表，$$7$$所在的位置是**原来是空白**，那么$$7$$一定是被**撞下来的**
我们把这样的操作称为碰撞操作

**删除算法**
将$$(s, t)$$删去，注意，此时$$(s, t)$$一定是一个边角，令$$x = P(s, t)$$
1）如果当前在第一行，退出并删除$$x$$
2）否则，在**上一行**找到**最后一个$$< x$$的数$$y$$**
3）用$$x$$替换$$y$$的位置，然后$$x = y$$，重复操作2

注意，插入$$x$$保证了插入的数$$x$$代替了**第一个$$> x$$**的位置，来看一下会发生什么
首先找到第一个满足`x < ?`的`?`，然后`?`发生碰撞，把另一个数撞到边角
这个数满足什么特点呢？不妨设`? < y`，`y`会被撞到边角

删除的时候，从边角开始删
这样我们先考虑`y`，根据删除操作，`y`要在上一行找到最后一个$$< y$$的数
注意到这样的数实际上就是`?`
所以删除和插入互为逆运算

**碰撞序列**
插入 8 的碰撞序列定义如下
![](/media/content_img/youngtable2.png)

关于碰撞序列 $$x = x\_1 < x\_2 < \cdots < x\_s < x\_{s+1} = \infty$$
还可以构造出一个由下标组成的辅助序列 $$r_1 \geqslant r_2 \geqslant \cdots \geqslant r_s = t$$

其中$$1 \leqslant i \leqslant s$$，并且元素$$P(x, r\_i)$$已经由$$x\_{i+1}$$改成了$$x\_i$$

## 杨表的基本性质
**定理A**
在以下两者之间存在一一对应，一方是$$\\{1, 2, \cdots, n\\}$$的**所有排列**构成的集合
另一方是$$\\{1, 2, \cdots, n\\}$$构成的有序图表$$(P, Q)$$的集合，其中$$P, Q$$形状相同

**先来看怎么证明**
给定任意两行阵列
```math
\begin{pmatrix}
q_1 & q_2 & \cdots & q_n \\
p_1 & p_2 & \cdots & p_n
\end{pmatrix}
```
其中满足$$q_1 < q_2 < \cdots < q_n$$，并且$$p_1, p_2, \cdots p_n$$各不相同（一般情况是排列）

那么我们可以构造两个相应的图表$$P, Q$$，其中$$P$$的元素是$$(p_1, p_2, \cdots ,p_n)$$
而$$Q$$中的元素是$$(q_1, q_2, \cdots, q_n)$$，$$P, Q$$的形状相同

设$$P, Q$$初始都为空，接下来对$$i = 1, 2, \cdots, n$$进行以下操作
用**插入算法**将$$p_i$$插入杨表$$P$$
然后我们令$$Q(s,t) = q_i$$（这里是对应放入，不涉及算法），这里$$s, t$$是$$P$$中新填充的位置
比如形如
```math
\begin{pmatrix}
1 & 3 & 5 & 6 & 8 \\
7 & 2 & 9 & 5 & 3
\end{pmatrix}
```
![](/media/content_img/youngtable3.png)

因为杨表插入和删除操作是可逆的，不妨设$$Q$$的元素是$$q_1 < q_2 < \cdots < q_n$$
对$$i = n, n-1, \cdots, 2, 1$$逆着执行算法，同样可以构造出$$(P, Q)$$
**这里的对应关系，指的是$$(P, Q)$$对应**
![](/media/content_img/youngtable4.png)

### 杨表的子结构
注意到，一旦一个元素被**碰撞到**第二行，它对第一行是没有任何影响的
所以第二行以下又可以单独来看，比如上面的例子，**被碰撞**的元素分别是$$5, 9, 7$$
从而对于$$P, Q$$，除去第一行之后的阵列分别是
```math
\begin{pmatrix}
3 \ 6 \ 8 \\
7 \ 9 \ 5
\end{pmatrix}
```
恰好对应上述子矩阵的杨表

> 这个杨表怎么来的？还是看对应关系，第一行可以认为是时间戳，第二行是数
在$$3$$时刻，插入$$2$$，撞下$$7$$，得到$$(3, 7)$$
在$$6$$时刻，插入$$5$$，撞下$$9$$，得到$$(6, 9)$$
在$$8$$时刻，插入$$3$$，撞下$$5$$，得到$$(3, 5)$$

```math
\begin{pmatrix}
1 \ 3 \ 5 \ 6 \ 8 \\
7 \ 2 \ 9 \ 5 \ 3
\end{pmatrix}
```

> 观察后发现，原阵列中，删去第一行的$$2, 3$$，然后下方每个元素尝试右移，填补空缺，好像就得到了碰撞子矩阵？

## 杨表的分类
如果一个空图表$$P$$开始，逐次对$$p_1, p_2, \cdots p_i$$应用**插入算法**之后
有$$p_i = P(1, t)$$，那么称$$(q_i, p_i)$$相对于两行阵列
```math
\begin{pmatrix}
q_1, q_2, \cdots, q_n \\
p_1, p_2, \cdots, p_n
\end{pmatrix}
\quad \quad \textbf{(1)}
```
（其中$$q_1 < q_2 <\cdots < q_n$$并且$$p_1, p_2\cdots, p_n$$各不相同）
**属于第$$t$$类**，默认插入算法总是把给定元素插入第$$1$$行

**性质**
容易看出，当且仅当$$p_i$$有$$i-1$$个**反序**，即$$p_i = \min (p_1, p_2, \cdots, p_i)$$
是一个**前缀最小值**的时候，$$(q_i, p_i)$$属于第$$1$$类

**考虑子结构**
我们定义这样的阵列形态为**父亲**，考虑舍去父亲中**属于第一类的列**
得到一个儿子阵列
```math
\begin{pmatrix}
q_1^{\prime}, q_2^{\prime}, \cdots, q_m^{\prime} \\
p_1^{\prime}, p_2^{\prime}, \cdots, p_m^{\prime}
\end{pmatrix}
```
那么儿子阵列中$$(p, q)$$属于第$$t$$类，当且仅当它相对于父亲阵列属于第$$t+1$$类
比如上述的杨表
```math
\begin{pmatrix}
3, 6, 8 \\
7, 9, 5
\end{pmatrix}
```
满足$$p_i$$恰好等于**前缀最小值的有**$$\\{7, 5\\}$$，从而
第一类是$$\\{(3, 7), (8, 5)\\}$$，第二类是$$\\{(6, 9)\\}$$

**子结构的性质**
对于任何固定的$$t$$，第$$t$$类的元素可以标记为
```math
(q_{i1}, p_{i1}), (q_{i2}, p_{i2}), \cdots, (q_{ik}, p_{ik})
```
其中$$q\_{i1} < q\_{i2} < \cdots < q\_{ik}$$，并且$$p\_{i1} > p\_{i2} > \cdots > p\_{ik} \quad \quad \textbf{(2)}$$

其实不难理解，因为要满足$$p\_{i} = \min(p\_{1}\cdots p\_{i})$$，所以关于$$p$$是**单调递减的**
另外$$q$$序列可以看成构造时候的时间戳，在构造结束的时候，有
$$p(1, t) = p\_{ik}, \quad Q(1, t) = q\_{i1}$$（$$Q$$的构造不涉及到算法，只是对应位置放入）

最后在关于**第一行**$$P(1, t)$$的位置是$$p\_{ik}$$，另一方面，被**撞下**的阵列确定了$$P, Q$$的下面两行
```math
\begin{pmatrix}
q_{i_2}, q_{i_3}, \cdots, q_{i_k} \\
p_{i_1}, p_{i_2}, \cdots, p_{i_{k-1}}
\end{pmatrix}
```

## 杨表的其他性质，对合数
**性质一**
已知下标$$i_1, i_2, \cdots, i_t$$满足
```math
p_{i_1} < p_{i_2} < \cdots < p_{i_t} = p, \quad q_{i_1} < q_{i_2} < \cdots < q_{i_t} = q
```
当且仅当$$t$$取满足上述条件的最大值的时候，$$(p, q)$$属于第$$t$$类

**证明**
考虑插入过程，将$$p_i$$插入第$$i$$列时，不妨设第$$t-1$$列的元素是$$p_j$$
也就是说$$(q_j, p_j)$$是在第$$t-1$$类中，并且$$q_j < q_i$$
充分性，$$p_j < p_i$$，那么$$p_i$$不会发生碰撞，直接放在$$p_j$$后面，$$t$$会增加$$1$$
根据归纳法，存在满足该性质的下标$$(i_1, i_2, \cdots, i_t)$$
必要性，如果$$q_j < q_i$$并且$$p_j < p_i$$，此时再给个条件，$$(q_j,p_j)$$在$$t-1$$类中
那么插入$$p_i$$之后，不难发现列$$t-1$$中存在一个$$< p_i$$的元素，因此$$(q_i, p_i)$$在$$\geqslant t$$类中

**性质二 逆排列**
```math
\begin{pmatrix}
q_1, q_2, \cdots, q_n \\
p_1, p_2, \cdots, p_n
\end{pmatrix}^{-1} = 
\begin{pmatrix}
p_1, p_2, \cdots, p_n \\
q_1, q_2, \cdots, q_n
\end{pmatrix} \\
= \begin{pmatrix}
p_1^{\prime}, p_2^{\prime}, \cdots, p_n^{\prime} \\
q_1^{\prime}, q_2^{\prime}, \cdots, q_n^{\prime}
\end{pmatrix}
```
给定一个阵列，它的各个列基本上是独立的，重新排列，满足$$p\_{1}^{\prime} < p_2^{\prime} < \cdots < p_n^{\prime}$$

并且$$q\_{1}^{\prime}, q\_{2}^{\prime}, \cdots q\_{n}^{\prime}$$各不相同

那么观察杨表$$\textbf{(1)}$$，不妨把之前的杨表记为$$(P, Q)$$
交换两行，并且按各列排序，使得新阵列的上行呈现增序，这样的阵列对于$$\textbf{(1)}$$称为**逆阵列**
逆阵列对应的图表恰好为$$(Q, P)$$

**证明**
不难证明，假设$$(p, q)$$属于第$$t$$类，我们依然有
```math
p_{i_k} < \cdots < p_{i_2} < p_{i_1} \\
q_{i_k} > \cdots > q_{i_2} > q_{i_1}
```
那么相应地，$$P(1, t) = q\_{i\_1}, Q(1, t) = p\_{i\_k}$$

> 不知道发现没有，$$P(1, t)$$在$$t$$类中，要满足$$p\_i = \min(p\_1\cdots p\_i)$$
所以关于$$P(1, t)$$，取$$t$$类满足条件的最小的$$p$$，对于逆阵列，$$p, q$$互换
相当于取最小的$$q$$，就是$$q\_{i\_1}$$
同理，$$p$$在互换后，相当于时间戳，$$Q(1,t)$$也要取最小的$$p$$，就是$$p\_{i\_k}$$

不难发现，被撞下的元素是$$q\_{i\_2} < q\_{i\_3} \cdots < q\_{i\_k}$$，形成撞下的阵列

```math
\begin{pmatrix}
p_{i_{k-1}} & \cdots & p_{i_2} & p_{i_1} \\
q_{i_k} & \cdots & q_{i_3} & q_{i_2}
\end{pmatrix}
```
> 发现没？留在第一行的只有$$(p\_{i\_k}, q\_{i\_1})$$，相当于“错位了”

**对合数的性质**
对于对合排列$$P$$，$$P$$中满足$$P_i = i$$的$$i$$数量等于**它所对应的杨表奇数列的个数**

可以证明如下
![](/media/content_img/youngtable5.png)
![](/media/content_img/youngtable6.png)

## 删除角落元素和对偶
### 删除角落元素
1）初始化，令$$(s, t) = (1, 1)$$
2）移去该元素，**检查刚空出来的位置，相应的正下方和正右方的元素**，移动其中较小的那个
3）反复上面那个过程，直到$$P(r, s) = \infty$$，算法结束

该算法不妨称为算法$$S$$
下面是算法流程的例子
![](/media/content_img/youngtable7.png)

**定理**
如果$$P$$是由排列$$a\_1, a\_2, \cdots, a\_n$$根据定理 A 构造的图表，并且$$a\_i = \min \\{a\_1, a\_2, \cdots, a\_n\\}$$
那么算法 S 将图表 P 转化为对应于$$a\_1\cdots a\_{i-1}a\_{i+1}\cdots a\_n$$的图表

**证明**
不妨设$$a\_1a\_2\cdots a\_{i-1}a\_{i+1}\cdots a\_n$$构成排列$$Q$$，考虑到$$a\_i = 1$$
那么可知$$Q \leftarrow 1$$形成图表$$P$$
此时$$1$$撞下$$2$$，形成图表$$P$$，观察第一行，发现以下几个性质
1）$$1$$是最小元素，一定在左上角 2）除了$$1$$之外，$$P,Q$$第一行相同
唯一的不同在于$$P\_{1, 1} = 1, Q\_{1, 1} = 2$$

接着看$$P^S$$，删除$$1$$，那么$$2$$接管其位置，其他位置不变
我们有$$P^S\_{1,1} = 2, Q\_{1, 1} = 2$$，可以发现，第一行，$$P^S, Q$$完全相同

因为$$2$$被撞下，$$2$$又是剩余元素中最小的，对行归纳，不难发现$$P^S, Q$$是对应的

至于$$a_j = 2, j > i$$的情况，对图表**转置**，同理可证

## 杨表和最长上升子序列
**这个问题很重要**，用杨表来解决 LIS 和 LDS 问题，是基本思路
### 相关引理
**引理 1**
如果用$$\rightarrow$$表示对列插入，$$\leftarrow$$表示对行插入
那么我们有$$(x \rightarrow S) \leftarrow y = x \rightarrow (S \leftarrow y)$$
![](/media/content_img/youngtable8.png)

**引理 2**
对于一个排列$$X$$，它所对应的杨表是$$P$$，若$$X^R$$是$$X$$的翻转
那么$$X^R$$对应的杨表是$$P^T$$，其中$$P^T$$是关于$$P$$的转置
![](/media/content_img/youngtable9.png)

证明的过程，可以用归纳法
```math
P(x_1, x_2, \cdots, x_n, x_{n+1}) = P^{\prime}(x_1, x_2, \cdots, x_n) \leftarrow x_{n+1} \\
=(x_1 \to P^{\prime} (x_2\cdots x_n)) \leftarrow x_{n+1} \\
= x_1 \to P^{\prime}(x_2\cdots x_nx_{n+1}) \\
= P^{\prime}(x_1, x_2, \cdots, x_{n+1})
```

### LIS 和 LDS 相关重要结论
**定理 1**
杨表$$P_X$$中，第一行长度即为$$X$$的 LIS（最长上升子序列） 长度

**定理 2**
杨表$$P_X$$中，第一列长度即为$$X$$的 LDS (最长下降子序列) 长度

证明
把序列翻转之后，原先的最长上升子序列就成了最长下降子序列
对应的杨表也要转置，这个结论可以立刻得到

**定理 3**
定义 k-LIS 序列为 LIS 长度不超过 k 的序列，同理，定义 k-LDS 序列为 LDS 长度不超过 k 的序列

显然，最长的 1-LIS 子序列就是该序列的 LDS，对应杨表第一列的长度
前 k 列长度，就是最长的 k-LIS 子序列长度

## 杨表的对偶与转置
### 杨表的对偶
**定理（舒岑贝热）**
```math
\begin{pmatrix}
q_1 \ q_2 \ \cdots \ q_n \\
p_1 \ p_2 \ \cdots \ p_n
\end{pmatrix}
```
是对应于图表$$(P, Q)$$的两行阵列

1）对$$q$$而不对$$p$$应用对偶（颠倒）顺序，两行阵列
```math
\begin{pmatrix}
q_n \ \cdots \ q_2 \ q_1 \\
p_n \ \cdots \ p_2 \ p_1
\end{pmatrix}
```
对应于$$(P^T, (Q^S)^T)$$，其中$$T$$是转置操作，$$P^T$$是图表，$$(Q^S)^T$$是对偶图表
因为此时$$q$$的顺序是颠倒的

2）对$$p$$而不对$$q$$应用对偶顺序，阵列对应于$$((P^S)^T, Q^T)$$
3）对$$p, q$$同时应用对偶顺序，那么阵列对应于$$(P^S, Q^S)$$

### 证明几个引理
**引理1**
不妨设$$a\_1 a\_2 \cdots a\_{j-1}a\_j\cdots a\_n$$是不同元素的排列，并且假定$$1 < j \leqslant n$$
交换$$a\_{j-1}, a\_j$$得到排列$$a\_1\cdots a\_{j-2}a\_ja\_{j-1}a\_{j+1}\cdots a\_n$$
交换是**可接受的**，当满足以下条件
1）$$j \geqslant 3$$并且$$a\_{j-2}$$的值介于$$a\_j, a\_{j-1}$$之间
2）$$j < n$$并且$$a\_{j+1}$$的值位于$$a\_{j-1}$$与$$a\_j$$之间

那么有以下结论
1）把元素$$a\_1, a\_2, \cdots a\_n$$依次插入初始为空的图表$$P$$，可接受交换并不会改变图表$$P$$
2）可以通过可接受交换，相互转换任何两个拥有相同图表$$P$$的排列

**证明1**
![](/media/content_img/youngtable10.png)

不难发现，可接受交换，变换之后，图表$$P$$的形状保持不变

**证明2**
等价于证明以下结论，设$$P$$的形状是$$(n_1,n_2, \cdots, n_m)$$，证明可以通过一系列可接受交换
将对应于$$P$$的排列转换为**规范排列**
```math
P_{m1} \cdots P_{mn_m} \ \cdots \ \ P_{21} \cdots P_{2n_2} \ P_{11}\cdots P_{1n_1}
```
即将杨表从下往上每一行依次写在后面

不难发现，对于一个很大的数$$A$$，如果有**连续单调递增的一段**，那么可以通过可交换排列，将$$A$$提到最前面

考虑最后一行（第$$m$$行），第一个元素令$$A \leftarrow P\_{m1}$$，在第$$m-1$$行
一定可以找到这样连续的段，使得$$x_1 < x_2 <\cdots < x_k$$，这样$$A$$可以通过可接受交换
**不断提前**，放到$$(m-1, 1)$$的位置上

对行归纳，可知$$P\_{m1}$$可以放到$$(1, 1)$$处，以此类推，对$$P\_{m2}$$可放到$$(1, 2)$$处，归纳可证

**引理2**
设$$P$$是对应排列$$a_1, a_2, \cdots, a_n$$的图表，$$P^T$$是对应$$a_n, \cdots, a_2, a_1$$的图表

证明不难，因为可接受交换左右对称，如果颠倒插入顺序，那么$$P$$对应的规范排列，显然就是$$P^T$$

### 对偶性的证明
情形1） 对某个对偶图表$$X$$，对$$q$$而不对$$p$$应用对偶顺序，相当于**倒着插入**
图表对应于$$(P^T, X)$$

情形2）对于某个对偶图表$$Y$$，可以先考虑用**逆变换**，转为图表$$(Q, P)$$
这样就变成了情形1），变换后的图表对应$$(Q^T, Y)$$，再逆变换回来，对应图表$$(Y, Q^T)$$
其中$$Y$$有$$P^T$$的形状

接着我们考虑$$Y$$到底是多少（注意，我们对$$p$$应用了**对偶**顺序），那么有以下几个性质
1）不妨设$$p_i = \min\\{p_1, p_2, \cdots, p_n\\}$$，那么**对偶顺序**下，$$p_i$$就是最大的元素
那么$$p_i$$插入$$Y$$的过程中，不会撞下任何元素，它出现在$$Y$$的外围

我们来看插入过程，根据不同的顺序插入

对偶序：$$p\_1\cdots p\_{i-1}p\_{i+1} \cdots p\_n$$，得到$$Y - \\{p_i\\}$$

正常序：$$p\_1\cdots p\_{i-1}p\_{i+1}\cdots p\_n$$，得到$$d(P)$$，即$$P$$删除最角落元素得到的杨表

那根据之前，**算法S** 的讨论，我们对$$d(P)$$执行算法S，可以得到$$P$$的对偶

可以写出$$d(P)^S \to \\{ \text{对偶序} \\}$$，同时$$(d(P)^S)^T \to \\{ \text{对偶序} \\}^T$$

因为$$Y$$具有形式$$P^T$$，对$$n$$归纳，可以知道$$(d(P)^S)^T = Y - \\{p_i\\}$$

2） 另一方面，根据操作S，知道$$p_i$$位于最外围，所以有$$(P^S)^T - \\{p_i\\} = (d(P)^S)^T$$
那么有$$Y = (P^S)^T$$

3）这样就证明了以上定理，根据操作S的**行列对称性**，我们有$$(P^S)^T = (P^T)^S$$

### 重要的结论
往空图表逐次插入互不相同的$$p_1, p_2, \cdots, p_n$$得到图表$$P$$
以相反顺序插入，可以得到**转置图表**$$P^T$$
如果不仅以$$p_n\cdots p_1$$的顺序插入$$p$$，在插入的过程中交换$$> , <$$以及$$0, \infty$$的作用
会得到对偶图表$$P^S$$

## 杨表相关的计数问题
在由$$\\{1,2,\cdots, n\\}$$生成的图表中，有多少具有给定形状$$(n_1, n_2, \cdots, n_m)$$
其中$$n_1 + n_2 + \cdots + n_m = n$$，如果用$$f(n_1, n_2, \cdots, n_m)$$表示方案数
并且允许$$n_j$$为任意整数，那么$$f$$满足以下关系

除非$$n_1 \geqslant n_2 \geqslant \cdots \geqslant n_m \geqslant 0$$，否则$$f(n_1, n_2,\cdots, n_m) = 0$$
另外，$$f(n_1, n_2, \cdots, n_m, 0) = f(n_1, n_2, \cdots, n_m)$$

如果$$n_1 \geqslant n_2 \geqslant \cdots \geqslant n_m \geqslant 1$$，那么
```math
f(n_1,n_2, \cdots, n_m) = f(n_1-1, n_2,\cdots n_m) + f(n_1, n_2-1,\cdots, n_m) + \cdots + f(n_1, n_2, \cdots n_m - 1)
```
这个式子的证明，基于一个事实，因为**删除一个杨表中的最大元素，总会得到另一个杨表**
方案数就是枚举删哪一行，然后加起来

### 勾子函数
如果给出相对宽松的条件，$$n_1 + m - 1 \geqslant n_2 + m - 2 \geqslant \cdots \geqslant n_m$$
满足这些关系的函数$$f(n_1, n_2, \cdots, n_m)$$有一种简单的形式
```math
\displaystyle
f(n_1, n_2, \cdots, n_m) = \dfrac{\Delta(n_1 + m - 1, n_2 + m-2, \cdots, n_m) \cdot n!}{(n_1 + m - 1) !(n_2 + m - 2) ! \cdots n_m!}
```
其中，$$\Delta$$是范德蒙行列式，叫做判别式的平方根函数
```math
\Delta(x_1, x_2, \cdots, x_m) = \det \begin{pmatrix} x_1^{m-1} & x_2^{m-1} & \cdots & x_m^{m-1} \\
\vdots & \vdots & \vdots & \vdots \\ 
x_1^2 & x_2^2 & \cdots & x_m^2 \\
x_1 & x_2 & \cdots & x_m \\
1 & 1 & \cdots & 1\end{pmatrix} = \prod_{1 \leqslant i < j \leqslant m} (x_i - x_j)
```
**勾子定理**
对所有形状求和，两步走，第一步是确定杨表的形状，即确定$$Q$$
第二步，确定合适的排列，填入$$Q$$中，即确定$$P$$，这样确定了$$(P, Q)$$，求和
```math
\displaystyle
n! = \sum_{\begin{aligned} k_1 \geqslant k_2 \geqslant \cdots k_n \geqslant 0 \\
k_1 + k_2 + \cdots k_n = n\end{aligned}} f(k_1, k_2, \cdots, k_n)^2 \\
= n!^2 \sum_{\begin{aligned} k_1 \geqslant k_2 \geqslant \cdots \geqslant k_n \geqslant 0 \\
k_1 + k_2 + \cdots + k_n = n\end{aligned}} \dfrac{\Delta(k_1+n-1, k_2+n-2, \cdots k_n)^2}{(k_1+n-1)!^2(k_2+n-2)!^2 \cdots k_n!^2} \\
=n!^2 \cdot \sum_{\begin{matrix} q_1 > q_2 > \cdots > q_n > 0 \\
q_1 + q_2 + \cdots + q_n = (n+1)n /2\end{matrix}} \dfrac{\Delta(q_1, q_2, \cdots, q_n)^2}{q_1!^2 q_2!^2 \cdots q_n!^2}
```
因此
```math
\displaystyle
\sum_{\begin{matrix} q_1+q_2 +\cdots + q_n = n(n+1)/2 \\
q_1, q_2, \cdots, q_n \geqslant 0\end{matrix}} \dfrac{\Delta(q_1, q_2, \cdots q_n)^2}{q_1!^2 q_2!^2 \cdots q_n!^2} = 1
```
注意到关于$$q$$是对称的，当$$q_i = q_j$$时，$$\Delta = 0$$

![](/media/content_img/youngtable11.png)

定义**钩子长度**$$hook(x)$$，为$$x$$右方所有格子的个数，以及$$x$$下方所有格子的个数，再加上$$1$$（$$x$$本身）
对图进行观察，不难发现第一行包含$$\\{n_1+m-1, n_2+m-2 \cdots 1\\}$$中，除去
```math
\begin{matrix}
(n_1+m-1)-(n_m) \\
(n_1+m-1)-(n_{m-1}+1) \\
\vdots \\
(n_1+m-1)-(n_2+m-2)
\end{matrix}
```
之外所有长度，以此类推，第$$j$$行包括$$\\{n_j+m-j,\cdots, 1\\}$$中除去
```math
\begin{matrix}
(n_j + m - j) -(n_m) \\
\vdots \\
(n_j+m-j)-(n_{j+1}+m-j-1)
\end{matrix}
```
外所有的元素
换句话说
```math
\displaystyle
\prod hook(x) = \dfrac{(n_1+m-1)!(n_2+m-2)!\cdots n_m!}{\Delta(n_1+m-1, n_2+m-2, \cdots , n_m)}
```

### 钩子定理
由$$\\{1, 2, \cdots, n\\}$$生成的具有指定形状的图表数目是
```math
\displaystyle
f = \dfrac{n!}{\prod_{x \in Young} hook(x)}
```

## 牛客小白月赛104
### C
**[小红打怪](https://ac.nowcoder.com/acm/contest/94879/C)**
**算法分析**
不难想到用二分来做，注意到每一轮，第一次一定是用全局 AOE 削减所有怪物血量
所以可以将数组`a`都减去`mid`，然后存放到数组`b`中，考虑怎么写`check`

对于数组`b`，每一次只需要考虑队友 1， 2 的操作即可
由于队友 1 一回合可以削减 2 个怪物的血量，不难想到贪心地，优先处理$$b\_i > 0, b\_{i+1} > 0$$的情形

策略如下，队友 1 优先处理$$b\_{i} > 0, b\_{i+1} > 0$$的怪物，看看在`mid`回合内，
最多能处理掉多少怪物
如果回合数`mid`刚好用完，剩下的只能交给队友 2 处理
如果还剩下`rem`个回合，那么队友 1，队友 2 就共同打怪

因为一共`mid`回合，队友 2 不论如何都可以打掉`mid`的血量
区别就在于，如果有**剩余`rem`回合**，队友 2 可以**辅助队友 1**，在剩余回合中，队友 2 可以辅助削减`rem`血量
判断一下剩下来的怪物`sum += b[i]`，`mid + rem >= sum`是否成立即可

## AtCoder Beginner Contest 378
**[G - Everlasting LIDS](https://atcoder.jp/contests/abc378/tasks/abc378_g)**
**问题描述**
给你一个$$1 \sim AB-1$$的排列，问满足以下条件的，这样的排列的方案数
排列的 LIS 是 A，LDS 是 B
存在一个$$n$$，使得将$$n+0.5$$插入排列之后，LIS, LDS 不变

### 算法分析
考虑杨表，原排列构成$$AB-1$$的杨表
也就是说，存在一个$$n$$，当$$n+0.5$$插入杨表之后，杨表的形状恰为$$A \times B$$
注意到，必然会发生碰撞，但是被撞下的元素，最后又恰好能够插入到杨表的**末尾空缺**
也就是能够顺利插入$$(B, A)$$这个位置 （`LDS = B, LIS = A`，对应$$B$$行$$A$$列）

> 杨表被撞下的元素有什么特点

![](/media/content_img/youngtable12.png)

根据杨表的性质，形状`L`位置上的数都$$< x$$，那么如果能够成功构造$$B \times A$$
首先就有`B-1`行被撞下的元素$$? > t\_{B, A-1}$$，那么$$?$$只能够来自第$$A$$列

另外，题中分析，要想从$$BA-1$$构造出$$BA$$，从第一行插入$$(n+0.5)$$之后
第$$1 \sim B-1$$行都会发生碰撞，且撞下的元素都来自第$$A$$列
根据上面的分析，从$$B \to 1$$**对行归纳**，可以杨表必须满足
```math
t_{i+1, A-1} < t_{i, A}, \quad i \in [1, B-1]
```

> 接着考虑怎么实现呢？

首先用**钩子函数**，计算出具有该形状的杨表的方案数，记为`ans`，此时统计的是$$Q$$的方案数

接着计算满足条件的$$P$$的方案数，这可以用暴力 dp 来统计
**维护图表，从左往右，按列的顺序依次从大到小放置元素，满了就不放**

用`vector tb`模拟杨表，考虑$$tb \to ntb$$
令$$tb_i$$表示当前的杨表状态，第$$i$$列长度是$$tb_i$$（放了$$tb_i$$行）

```bash
let ntb = tb
if tb(i) < B and tb(i) < tb(i-1)，或者是 i = 0，第 i 列可能可以继续放置，具体行不行呢
		if i = A 在最后一列，并且 tb(i-1) - 1 == tb[i]
			那么这最后一列放满了，不能放了，跳过
			
		其他情况，ntb(i) += 1, dp( ntb ) += dp( tb )
```
用一个`map`暴力维护杨表，`dp( tb ) = f`，表示具有如`tb`形状的杨表的方案数
转移很简单，$$dp(ntb) += dp(tb)$$

迭代$$BA - 1$$次，用滚动数组，即可得到答案

上一篇：codeforces上的dp题（四）下一篇：2024-11月一些算法比赛（一）

看完文章有啥想法