题解：P16583 [GKS 2016 #B] Sherlock and Permutation Sorting

· · 题解

原题还是很简单的。

一个位置 i\in[1,n) 可以分段，当且仅当 \max\limits_{j=1}^i\{p_j\}<\min\limits_{j=i+1}^n\{p_j\}，不同的 i 显然是互不影响的，因此 f(p) 就等于合法的 i 个数 +1。

对于最靠右的一段，它一定包含了一段连续的值域后缀 [n-m+1,n]，并且不能继续拆分。设长为 n 的不可拆分的排列个数为 f_n，易知有 f_n=n!-\displaystyle\sum_{i=1}^{n-1}f_i\cdot(n-i)!。

设 A(x)=\displaystyle\sum_{i=0}^{+\infty}i!\cdot x^i，F(x)=\displaystyle\sum_{i=0}^{+\infty}f_i\cdot x^i（令 f_0=0），那么有 F=A-(FA-F)-1，即 F=1-\dfrac1A。

排列 p 的最优划分由若干个不可拆分的排列组成（Sequence 构造），直接算 m 次方和不太好做，转成下降幂，所有长为 n 的排列 p 的 f(p)^{\underline{k}} 之和为 [x^n]\displaystyle\sum_{i=0}^{+\infty}i^{\underline{k}}\cdot F^i=[x^n]\dfrac{k!F^k}{(1-F)^{k+1}}=k![x^n]A(A-1)^k，因此答案为：

[x^n]A\sum_{k=0}^m{m\brace k}k!(A-1)^k

对于本题，取 m=2，有答案为 [x^n]A(2A^2-3A+1)，直接卷即可，要写任意模数多项式乘法，复杂度为 \mathcal O(n\log n)。

如果 m 开到 \mathcal O(n) 也是可以做的，由于 [x^0](A-1)=0，直接多项式复合即可，复杂度为 \mathcal O(n\log^2n)。