Prutekoi's blog

杨表是指第 $i$ 行有 $\lambda_i$ 个格子，满足 $\lambda_i\geq \lambda_{i+1}$，且每一行填的数都递增，每一列都递增的网格。

因为排列对杨表有一个插入和删除算法，可以生成两个形状相同的杨表 $P$ 和 $Q$，所以每一对形状相同的杨表与一个排列一一对应。$n!=\sum f_{\lambda}^2$，$f_{\lambda}$ 表示 $\lambda$ 这种形状的杨表填数的方案数。

而两个完全相同的杨表 $P,Q$ 运用删除算法可以生成唯一一个自反的排列（看成置换，则自己是自己的逆置换），而一个自反的排列可以运用插入算法生成唯一一对相同的杨表。这说明大小为 $n$ 的杨表与自反排列有双射关系。（怎么证明我也不知道啊啊啊啊啊啊），而自反排列数有一个显然的递推 $a_n=a_{n-1}+(n-1)a_{n-2}$，于是这也是杨表个数的递推。

对一个排列 $p$ 作用插入算法生成的杨表 $P,Q$，$P$ 的第一行的元素数就是排列的最长上升子序列的长度。第一列元素数就是最长下降子序列的长度。

钩子公式：在一个固定形状，大小为 $n$ 的杨表中设 $h(i,j)$ 表示形如 $(x,y),x\geq i,y=j$ 或 $x=i,y\geq j$ 的格子的数量，则填数的方案数有 $f_{\lambda}=\frac{n!}{\prod h(i,j)}$。于是我们可以根据定义 $O(n^2)$ 计算一个形状的杨表填数方案数了。

而如果我们想要只用 $\lambda$ 表达，公式可以写成 $n!\frac{\prod_{1\leq j<k\leq m}(\lambda_j-j-\lambda_k+k)}{\prod_{i=1}^m(\lambda_i+m-i)!}$

这个怎么理解呢？大概就是关注分母上的 $(\lambda_i+m-i)!$，这个是尝试做完第 $i$ 行所有格子的贡献（第 $i$ 行格子的钩子长度的倒数积），然后对于不存在的长度，上面一定会有一个，就给消掉了。这个过程可以看成沿着杨表的边缘走，每向右走一格就会有一个正确的贡献没有被消掉。比较抽象，画图理解。

而EI说对钩子公式还有 $O(n)$ 的计算方法，不太懂啊QAQ。于是对于与LIS有关的计数，我们有杨表与排列的对应关系，还有杨表第一行与LIS的对应关系，还有杨表的形状只有整数划分数个，还有钩子公式来计数，就可以很优秀地计数啦！（因为整数划分数很小）

钩子公式的 $O(n)$ 计算很简单的。。。其实就是怎么 $O(1)$ 得到一个格子下面有几个格子。根据杨表形状中的单调性，发现不用数据结构维护。于是我们从下到上，从右到左计算，同时维护一个数组就行了。。论文里怎么回事，说要 $O(n^2)$ 计算。。

于是这题就可以踩标算了233

#include<bits/stdc++.h>
using namespace std;
const int N=100,mod=998244353;
int n,a[N],b[N],m,ans,J,inv[N];
void solve(){
    int ret=J;
	for(int i=1;i<=a[1];i++)b[i]=0;
    for(int i=m;i;i--){
        for(int j=a[i],dat=0;j;j--)
            dat+=b[j]+1,ret=1ll*ret*inv[dat]%mod;
		b[a[i]]++;
    }
    ans=(ans+1ll*ret*ret%mod*a[1])%mod;
}
void dfs(int x,int y){
    if(!x){solve();return;}
    for(int i=min(y,x);i;i--)a[++m]=i,dfs(x-i,i),m--;
}
int main(){
    scanf("%d",&n);inv[1]=J=1;int st=clock();
    for(int i=2;i<=n;i++)J=1ll*J*i%mod,inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;
    dfs(n,n);for(int i=1;i<=n;i++)ans=1ll*ans*inv[i]%mod;
    cout<<ans<<" "<<clock()-st;
    return 0;
}

（打出来一个浮点数表闲的吧）

1 1,
2 1.5,
3 2,
4 2.41667,
5 2.79167,
6 3.14028,
7 3.46528,
8 3.77034,
9 4.05935,
10 4.33496,
11 4.59886,
12 4.85238,
13 5.09669,
14 5.3328,
15 5.56153,
16 5.78354,
17 5.99942,
18 6.20965,
19 6.41467,
20 6.61487,
21 6.81058,
22 7.0021,
23 7.1897,
24 7.37362,
25 7.55406,
26 7.73124,
27 7.90531,
28 8.07646,

关于杨表还有很多牛逼的东西，具体可以看2019论文，但是看起来OI里用不太到啊QAQ