思路
看到排列和 LIS，所以想到了杨表。
设杨图单元格数为 ，则其每一行的格数构成了 的一种整数划分。
向一个单元格数为 ，划分为 的杨图 中，插入 的排列，我们有钩长公式，得到的标准杨表的数量 为：
此时对应排列的 LIS 长度，为杨表第一行的长度 。
对于划分都为 的杨表，我们有 Robinson-Schensted correspondence 定理，它们中两两会唯一对应一种排列。则 对答案的贡献为：
我们钦定杨图的形态，则答案为：
由于 ，最多也就 种划分，所以暴力枚举 即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| inline void dfs(int las,int num){
if(num==n){
ll val = mul;
for(int i=1;i<=cnt;++i){
for(int j=1;j<=Y[i];++j){
int num = Y[i]-j+1,t = i+1;;
while(t<=cnt && Y[t]>=j) ++t,++num;
(val *= inv[num])%=mod;
}
}
(val *= val*Y[1]%mod)%=mod;
(ans += val)%=mod;
}
for(int i=1;i<=las;++i){
if(num+i>n) break;
Y[++cnt] = i;
dfs(i,num+i);
--cnt;
}
}
int main(){
read(n); mul = 1;
for(ll i=1;i<=n;++i) (mul *= i)%=mod;
for(int i=1;i<=n;++i){
Y[++cnt] = i;
dfs(i,i);
--cnt;
}
(ans *= quick_pow(mul,mod-2))%=mod;
printf("%lld",ans);
return 0;
}
|