杨表学习笔记
简介
杨表（Young tableau）是一种常用于表示论和舒伯特演算中的组合对象，在数学中被用于对称群和一般线性群的研究。阿尔弗雷德·杨（Alfred Young）于 1900 年提出了杨表。
杨图
定义
杨图（Young diagram）又称 Ferrers 图，是一个有限的单元格集合，其中每一行左对齐，且每一行的长度不严格递减（也有一种画法是不严格递增）。
设杨图的总单元格数为 \(n\)，则每一行的格数构成了 \(n\) 的一种整数分拆 \(\lambda\)。我们可以用 \(\lambda\) 表示杨图。
例如，\(\lambda=(5,4,1)\) 的杨图如下：
杨图中的每一个单元格用行数和列数唯一确定。在本文的画法中，行数、列数分别是从上往下、从左往右数；而在刚刚提到的另一种画法中，行数是从下往上数。换句话说，行数按单元格数从多到少的方向，列数从左对齐的方向。
对于 \(n\) 个单元格的杨图 \(\lambda\) 和 \(n-1\) 个单元格的杨图 \(\mu\)，若 \(\exists j,\textrm{s.t.}\forall i\ne j,\lambda_i=\mu_i,\lambda_j=\mu_j+1\)，记 \(\mu\uparrow\lambda\)。
臂长、腿长、勾长
杨图的每个单元格 \((x,y)\) 有臂长（arm length）、腿长（leg length）、勾长（hook length）：
- 臂长为这个单元格右面的单元格个数，记作 \(a_\lambda(x,y)\)。
- 腿长为这个单元格下面的单元格个数，记作 \(l_\lambda(x,y)\)。
- 勾长为这个单元格及其右面、下面的单元格总数，记作 \(h_\lambda(x,y)\)。由定义有 \(h_\lambda(x,y)=a_\lambda(x,y)+l_\lambda(x,y)+1\)。
杨表
定义
杨表（Young tableau）是用某个字母表的符号填充杨图得到的，字母表通常需要是全序集合。为了方便，一般填入正整数。
标准杨表（standard Young tableau）是满足每列数字严格递增、每行数字严格递增的杨表。
半标准杨表（semistandard / column-strict Young tableau）是满足每列数字严格递增、每行数字非严格递增的杨表。
标准杨表的 RSK 插入算法
RSK 插入算法由 Robinson、Schensted、Knuth 提出，它可以将杨表和排列联系起来。
要将 \(k\) 插入杨表 \(S\) 中，算法流程如下：
- 移动到第一行。
- 在该行中找到比 \(k\) 大的最小数 \(k'\)。
- 如果 \(k'\) 存在，将原本是 \(k'\) 的单元格替换为 \(k\)，然后令 \(k\gets k'\)，移动到下一行并重复步骤二。
- 如果 \(k'\) 不存在，将 \(k\) 放到该行末尾。
容易证明在上述算法过后，\(S\) 仍然是标准杨表。
杨表性质
将排列 \(p_1,p_2,\cdots,p_n\) 按 RSK 插入算法依次插入得到杨表 \(S\)，有性质：
- 第一行长度 \(S_1\) 为排列的 LIS 长度（内容不一定）。
- 第一列长度为排列的 LDS 长度（内容不一定）。
- 若将排列 \(p_n,p_{n-1},\cdots,p_1\) 插入杨表 \(S'\)，则 \(S'\) 是 \(S\) 交换行列得到。
- 更换全序集合的比较方式 \(\prec\) 为 \(\succ\)，杨表 \(S'\) 的形状是 \(S\) 交换行列得到（内容不一定）。
一些结论
勾长公式（hook length formula）
设有 \(n\) 个单元格的杨图 \(\lambda\)，在其中填入 \(1\sim n\) 的排列，得到的标准杨表数为 \(d_\lambda\)，则有：
\[d_\lambda=\frac{n!}{\prod h_\lambda(i,j)} \]例如，对于杨图 \(\lambda=(5,4,1)\)，有：
\[d_\lambda=\frac{10!}{7\cdot 5\cdot 4\cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot 1}=288 \]证明：（参考 杨表和钩子公式）
设 \(c_1,\cdots,c_m\) 为 \(h_\lambda(x,y)=1\) 的单元格，记 \(\mu_i=\lambda/\{c_i\}\)，则 \(\{\mu_1,\cdots,\mu_m\}=\{\mu\mid\mu\uparrow\lambda\}\)。
显然 \(d_\lambda=\sum\limits_{\mu\uparrow\lambda}d_\mu\)。设 \(e_\lambda=\frac{n!}{\prod h_\lambda(i,j)}\)，我们规定 \(d_\emptyset=e_\emptyset=1\)，只需证明 \(e_\lambda=\sum\limits_{\mu\uparrow\lambda}e_\mu\) 即可归纳得 \(d_\lambda=e_\lambda\)。
对 \(e_\lambda=\sum\limits_{\mu\uparrow\lambda}e_\mu\) 变形得 \(\sum\limits_{i=1}^m\frac{e_{\mu_i}}{e_\lambda}=1\)。
定义勾行走（hook walk）：
- 随机选取单元格 \((x,y)\in\lambda\) 作为起点。
- 每次从 \((x,y)\) 等概率地走到它下面、右面的共 \(h_\lambda(x,y)-1\) 格中的一个随机格子。
- 若不能再行走（即走到某个 \(c_i\)），则行走结束。
设随机事件 \(A_i\) 表示终点为 \(c_i\)，显然有 \(\sum\limits_{i=1}^mP(A_i)=1\)，只需证 \(P(A_i)=\frac{e_{\mu_i}}{e_\lambda}\)。
注意到 \(h_\lambda(x,y)+h_\lambda(x+1,y+1)=h_\lambda(x+1,y)+h_\lambda(x,y+1)\)，构造矩阵 \(h\)：
\[\begin{cases} h_{0,0}=0\\ h_{x,0},h_{0,y}\in\mathbb{N}^*\\ h_{x,y}=h_{x-1,y}+h_{x,y-1}-h_{x-1,y-1}\\ \end{cases} \]构造矩阵 \(p\)：
\[\begin{cases} p_{0,0}=1\\ p_{x,y}=\frac{1}{h_{x,y}}\left(\sum\limits_{i=0}^{x-1}p_{i,y}+\sum\limits_{j=0}^{y-1}p_{x,j}\right)\\ \end{cases} \]引理：\(\sum\limits_{i=0}^x\sum\limits_{j=0}^yp_{i,j}=\prod\limits_{i=0}^x\left(1+\frac{1}{h_{i,0}}\right)\prod\limits_{j=0}^y\left(1+\frac{1}{h_{0,j}}\right)\)。
证明：
容易验证 \(x,y\in\{0,1\}\) 成立。
有 \(h_{x,y}=h_{x,0}+h_{0,y}\)。设 \(S(x,y)=\sum\limits_{i=0}^x\sum\limits_{j=0}^yp_{i,j}\)，可以归纳知 \(S(x,0)\) 和 \(S(0,y)\) 时上式成立。
若 \(S(x-1,y),S(x,y-1),S(x-1,y-1)\) 上式均成立，则：
\[\begin{aligned} S(x,y)&=S(x-1,y)+S(x,y-1)-S(x-1,y-1)+p_{x,y}\\ &=S(x-1,y-1)\left(1+\frac{1}{h_{0,y}}+1+\frac{1}{h_{x,0}}-1\right)+\frac{1}{h_{x,y}}\left(\sum\limits_{i=0}^{x-1}p_{i,y}+\sum\limits_{j=0}^{y-1}p_{x,j}\right)\\ &=S(x-1,y-1)\left(1+\frac{1}{h_{0,y}}+\frac{1}{h_{x,0}}\right)+\frac{1}{h_{x,y}}(S(x-1,y)+S(x,y-1)-2S(x-1,y-1))\\ &=S(x-1,y-1)\left(1+\frac{1}{h_{0,y}}+\frac{1}{h_{x,0}}+\frac{1}{h_{x,0}+h_{0,y}}\left(\frac{1}{h_{0,y}}+\frac{1}{h_{x,0}}\right)\right)\\ &=S(x-1,y-1)\left(1+\frac{1}{h_{0,y}}\right)\left(1+\frac{1}{h_{x,0}}\right)\\ &=\prod\limits_{i=0}^x\left(1+\frac{1}{h_{i,0}}\right)\prod\limits_{j=0}^y\left(1+\frac{1}{h_{0,j}}\right)\\ \end{aligned} \]引理得证。\(\square\)
对于任意 \((x_0,y_0)\)，令 \(h_{x,0}=h_\lambda(x_0-x,y_0)-1,h_{0,y}=h_\lambda(x_0,y_0-y)-1\)，则有 \(h_{x,y}=h_\lambda(x_0-x,y_0-y)-1\)，\(p_{x,y}\) 为从 \((x_0-x,y_0-y)\) 走到 \((x_0,y_0)\) 的概率。
令 \((x_0,y_0)=c_i\)，则：
\[\begin{aligned} P(A_i)&=\frac{1}{n}\sum\limits_{x=0}^{x_0-1}\sum\limits_{y=0}^{y_0-1}p_{x,y}\\ &=\frac{1}{n}\prod\limits_{x=0}^{x_0-1}\left(1+\frac{1}{h_\lambda(x_0-x,y_0)-1}\right)\prod\limits_{y=0}^{y_0-1}\left(1+\frac{1}{h_\lambda(x_0,y_0-y)-1}\right)\\ &=\frac{\prod\limits_{x=0}^{x_0-1}h_\lambda(x_0-x,y_0)\prod\limits_{y=0}^{y_0-1}h_\lambda(x_0,y_0-y)}{n\prod\limits_{x=0}^{x_0-1}(h_\lambda(x_0-x,y_0)-1)\prod\limits_{y=0}^{y_0-1}(h_\lambda(x_0,y_0-y)-1)}\\ &=\frac{e_{\mu_i}}{e_\lambda} \end{aligned} \]\(\square\)
Robinson–Schensted correspondence
任意两个相同形状的杨表（填数可能不同），可以与排列建立一一对应。
即：
\[\sum\limits_{\lambda\in\mathcal P_n}(d_\lambda)^2=n! \]其中 \(\mathcal P_n\) 为 \(n\) 的所有分拆数，有结论 \(|\mathcal P_n|\sim\frac{1}{4\sqrt{3}n}\textrm{e}^{\sqrt{\frac{2n}{3}}\pi}\)（A000041）。
排列到双杨表的映射：
维护插入杨表 \(P\) 和记录杨表 \(Q\)。
依次枚举排列 \(p\) 中的元素 \(p_i\)，使用 RSK 插入算法将其插入 \(P\) 中。此时 \(P\) 中多了一个单元格，在 \(Q\) 的相同位置添加一个单元格并填入 \(i\)。
例如，\(p=[1,5,7,2,8,6,3,4]\) 得到的两个杨表如下：
双杨表到排列的映射：
根据填数从大到小枚举 \(Q\) 的单元格，从后往前确定排列 \(p\)。
枚举到一个单元格，在 \(P\) 中找到对应的单元格。若在第一行则直接删除，否则在上一行找到比它小的最大数，将它放到那里并继续删除被替换的数。
其实就是 RSK 插入算法的逆过程。
题目
CF1268B Domino for Young
给定一个杨图，求最多放多少不重叠的骨牌。
\(1\le n,\lambda_i\le 3\times 10^5\)。
题解
黑白染色，答案为更少的那种颜色个数。
引理：黑白相等的杨图可以被骨牌密铺。
证明：
放一个骨牌相当于删除两个相邻单元格。
若杨图为空，显然成立。
假设杨图有黑白格各 \(m-1\) 个时成立，下证黑白格各 \(m\) 个时成立。
若杨图存在两行格数相等，或存在两列格数相等，可以删除行/列末尾各一个单元格。显然可以找到这样的一对单元格，使得存在一个单元格 \((x,y)\) 满足 \(h_\lambda(x,y)=1\)，从而使得剩余部分仍然是杨图。
否则，\(\lambda=(k,k-1,\cdots,2,1)\) 黑白格数必然不等。
\(\square\)
当黑白不相等时，先按上述过程删成 \(\lambda=(k,k-1,\cdots,2,1)\)，我们删除顶端的格子然后继续做即可。显然顶端的格子一定是更多的那种颜色。
\(\square\)
复杂度为 \(\mathcal O(n)\)。
代码
// Problem: CF1268B Domino for Young
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1268B
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 3e5+5;
ll n, a[N], cnt[2];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int main() {
scanf("%lld", &n);
rep(i, 1, n) {
scanf("%lld", &a[i]);
cnt[i&1] += a[i] >> 1;
cnt[(i&1)^1] += a[i] - (a[i] >> 1);
}
printf("%lld\n", min(cnt[0], cnt[1]));
return 0;
}
P4484 [BJWC2018]最长上升子序列
求长度为 \(n\) 的随机排列 LIS 长度的期望。
\(1\le n\le 28\)。
题解
根据上文 Robinson–Schensted correspondence 中设计的映射算法，我们可以将排列一一对应为一对相同形状的杨表，其中杨表的第一行长度为 LIS 长度。
而对于杨图 \(\lambda\)，其杨表种类数为 \(d_\lambda\)，一对这种形状的杨表种类数为 \((d_\lambda)^2\)，杨表第一行长度为 \(\lambda_1\)。
于是所求被我们转化为：
\[\frac{1}{n!}\sum\limits_{\lambda\in\mathcal P_n}(d_\lambda)^2\lambda_1 \]我们有勾长公式，可以在 \(\mathcal O(n)\) 时间计算 \(d_\lambda\)：
\[d_\lambda=\frac{n!}{\prod h_\lambda(i,j)} \]另外前文提到，\(|\mathcal P_n|\sim\frac{1}{4\sqrt{3}n}\textrm{e}^{\sqrt{\frac{2n}{3}}\pi}\)，可以直接枚举。
于是复杂度为 \(\mathcal O(n|\mathcal P_n|)\)。
代码
// Problem: P4484 [BJWC2018]最长上升子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4484
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 30, mod = 998244353;
ll n, inv[N], fac, ifac, a[N], cnt[N], ans;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
ll calc(ll m) {
ll ans = fac;
rep(i, 1, m) rep(j, 1, a[i]) ans = ans * inv[a[i]-j+cnt[j]-i+1] % mod;
return ans;
}
void dfs(ll u, ll rem, ll lim) {
if(!rem) {
ll now = calc(u-1);
ans = (ans + now * now % mod * a[1] % mod) % mod;
return;
}
rep(i, 1, min(rem, lim)) {
a[u] = i; ++cnt[i];
dfs(u+1, rem-i, i);
}
rep(i, 1, min(rem, lim)) --cnt[i];
}
int main() {
scanf("%lld", &n);
fac = ifac = inv[0] = inv[1] = 1;
rep(i, 2, n) {
fac = fac * i % mod;
inv[i] = (mod - mod / i) * inv[mod%i] % mod;
ifac = ifac * inv[i] % mod;
}
dfs(1, n, n);
ans = ans * ifac % mod;
printf("%lld\n", ans);
return 0;
}
P3774 [CTSC2017]最长上升子序列
给定长度为 \(n\) 的数列 \(a\)，进行 \(m\) 次询问，每次询问一个 \(a\) 的 \(1\sim m\) 前缀的最长的满足 LIS 长度不超过 \(k\) 的子序列长度。
\(1\le n\le 5\times 10^4\)，\(1\le m\le 2\times 10^5\)。
题解·上（$95$ 分）
考虑扫描线，对询问按照 \(m\) 升序离线，每次加入一个数，问题转化为求当前数列的最长的满足 LIS 长度不超过 \(k\) 的子序列长度。
根据 Dilworth 定理（或者是对偶定理？分不清楚），对于有限偏序集，最长链中元素个数等于最小反链划分中反链个数。我们可以知道 LIS 长度不超过 \(k\) 等价于用不超过 \(k\) 个 DS 覆盖，从而将所求转化为杨表的前 \(k\) 列元素个数。
我们使用 RSK 插入算法维护杨表。这里虽然不是标准杨表，但是可以改造该算法使其能维护半标准杨表。然后使用树状数组维护每一列元素个数。
注意到 RSK 插入算法的复杂度为 \(\mathcal O(|\lambda|\log n)\)，因此这个算法的最坏复杂度为 \(\mathcal O(n^2\log n+m\log n)\)，实际得分 \(95\) 分。
代码·上（$95$ 分）
// Problem: P3774 [CTSC2017]最长上升子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3774
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n, m, a[N], ans[N];
vector<vector<int>> young;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Query {
int m, k, id;
}q[N];
struct BIT {
int c[N];
int lowbit(int x) {return x & (-x);}
void add(int x, int k) {for(; x < N; x += lowbit(x)) c[x] += k;}
int ask(int x) {int k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;}
}cnt;
void insert(int x) {
int sz = young.size();
if(!sz) {
young.push_back({x});
cnt.add(1, 1);
}
else {
for(auto& i : young) {
auto it = lower_bound(i.begin(), i.end(), x);
if(it == i.end()) {
i.push_back(x);
cnt.add(i.size(), 1);
return;
}
swap(*it, x);
}
young.push_back({x});
cnt.add(1, 1);
}
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, n) scanf("%d", &a[i]);
rep(i, 1, m) {
scanf("%d%d", &q[i].m, &q[i].k);
q[i].id = i;
}
sort(q+1, q+1+m, [](const auto& a, const auto& b) {
return a.m < b.m;
});
int j = 1;
rep(i, 1, n) {
insert(a[i]);
for(; j <= m && q[j].m == i; j++) ans[q[j].id] = cnt.ask(q[j].k);
}
rep(i, 1, m) printf("%d\n", ans[i]);
return 0;
}
题解·下（$100$ 分）
显然杨表的前 \(\sqrt{n}\) 行和前 \(\sqrt{n}\) 列可以覆盖整个杨表，考虑维护 \(\prec\) 关系的原杨表和 \(\succ\) 关系的转置杨表，分别维护前 \(\sqrt{n}\) 行。
每次加入元素就在两个杨表里同时插入，不过 RSK 插入算法只枚举前 \(\sqrt{n}\) 行即可，加到树状数组中的时候处理一下不要加重。
复杂度 \(\mathcal O(n\sqrt{n}\log n+m\log n)\)。
代码·下（$100$ 分）
// Problem: P3774 [CTSC2017]最长上升子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3774
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n, m, B, a[N], ans[N];
vector<vector<int>> youngA, youngR;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Query {
int m, k, id;
}q[N];
struct BIT {
int c[N];
int lowbit(int x) {return x & (-x);}
void add(int x, int k) {for(; x < N; x += lowbit(x)) c[x] += k;}
int ask(int x) {int k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;}
}cnt;
void insertA(int x) {
int szA = youngA.size();
if(!szA) youngA.push_back({x});
else {
for(auto& i : youngA) {
auto it = lower_bound(i.begin(), i.end(), x);
if(it == i.end()) {
i.push_back(x);
if((int)i.size() > B) cnt.add(i.size(), 1);
return;
}
swap(*it, x);
}
if(szA < B) youngA.push_back({x});
}
}
void insertR(int x) {
int szR = youngR.size();
if(!szR) {
youngR.push_back({x});
cnt.add(1, 1);
}
else {
int i = 0;
for(auto& r : youngR) {
++i;
auto it = upper_bound(r.begin(), r.end(), x, greater<int>());
if(it == r.end()) {
r.push_back(x);
cnt.add(i, 1);
return;
}
swap(*it, x);
}
if(szR < B) {
youngR.push_back({x});
cnt.add(i+1, 1);
}
}
}
void insert(int x) {
insertA(x);
insertR(x);
}
int main() {
scanf("%d%d", &n, &m); B = sqrt(n);
rep(i, 1, n) scanf("%d", &a[i]);
rep(i, 1, m) {
scanf("%d%d", &q[i].m, &q[i].k);
q[i].id = i;
}
sort(q+1, q+1+m, [](const auto& a, const auto& b) {
return a.m < b.m;
});
int j = 1;
rep(i, 1, n) {
insert(a[i]);
for(; j <= m && q[j].m == i; j++) ans[q[j].id] = cnt.ask(q[j].k);
}
rep(i, 1, m) printf("%d\n", ans[i]);
return 0;
}