- 求一个长度为(n)的随机排列的最长上升子序列长度期望。
- (nle28)
杨表与钩子定理
关于杨表的一些基础知识可见这篇博客：杨表的构造与基本性质。
着重需要了解一个性质，就是一张杨表及其记录表与排列一一对应，即两张形状相同的杨表与排列一一对应。
这里再介绍一下杨表的钩子定理。
定义一张形状为(lambda)的杨表中一个格子((i,j))的钩子函数(h_{lambda}(i,j))为它所在行右方格子数+它所在列下方格子数+它自身（因为长得像一个钩子，所以叫做钩子函数）。
而钩子定理为我们指出，一张形状为(lambdavdash n)的杨表数目，就是(frac{n!}{prod h_{lambda}(i,j)})。
暴枚杨表形状
对于这道题，我们首先暴枚杨表的形状，这一部分时间复杂度是(O(p(n)))的（(p(n))表示(n)的拆分个数，显然小于(2^n)）。
枚举出形状(lambda)之后，杨表第一行的长度(lambda_1)就是最长上升子序列长度，而这种形状的杨表个(f_{lambda})数可以直接钩子定理(O(n))计算。由于两张形状相同的杨表对应一个排列数，因此答案就是：
[frac1{n!}sum_{lambdavdash n}f_{lambda}^2 imeslambda_1
]
比需要本地打表才能过掉的状压(DP)不知道高明到哪去了。
代码：(O(np(n)))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 28
#define X 998244353
using namespace std;
int n,Fac,IFac,a[N+5],b[N+5],Inv[N+5];
I int Calc(CI c) {RI i,j,t=Fac;for(i=1;i<=c;++i) for(j=1;j<=a[i];++j) t=1LL*t*Inv[a[i]-j+b[j]-i+1]%X;return t;}//钩子定理计算杨表个数
int ans;I void dfs(CI c,CI x,CI lim)//暴枚杨表形状
{
if(!x) {RI t=Calc(c-1);ans=(ans+1LL*t*t%X*a[1])%X;return;}//统计答案，∑f^2×λ1
RI i;for(i=1;i<=min(lim,x);++i) ++b[a[c]=i],dfs(c+1,x-i,i);W(--i) --b[i];//划分，不能超过上行长度
}
int main()
{
RI i;for(scanf("%d",&n),Inv[1]=Fac=IFac=1,i=2;i<=n;++i)
Inv[i]=1LL*(X-X/i)*Inv[X%i]%X,Fac=1LL*Fac*i%X,IFac=1LL*IFac*Inv[i]%X;
return dfs(1,n,n),printf("%d
",1LL*ans*IFac%X),0;//除以总方案数计算期望
}