058B

posted on 2022-08-15 00:08:56 | under 题解 | source problem 一个长为 \(n\) 的排列 \(P\)，每次可以选择一个 \(i\)，令 \(v=\max(P_i,P_{i+1})\)，使 \(P_i=P_{i+1}=v\)，求若干次操作后有多少 ......

考虑从第 $b$ 列与第 $b + 1$ 之间分开这个矩阵，钦定 $(i, b)$ 下一步必须走到 $(i, b + 1)$，可以发现这样是不会漏算或算重的。 于是就可以用乘法原理算出这个 $i$ 的贡献：$\binom{(i - 1) + (b - 1)}{i - 1}\times \binom{ ......