题解：P14368 [JOISC 2018] 修行 / Asceticism
Greenzhe
·
·
题解
讲一下此题容斥“<”小于号的做法；记录了自己学习这篇题解时的疑问，补充了一些细节，并加入了一些自己的理解。
Description
给定 N,K(N \le 10^5)，求长度为 N 的、能划分成恰好 K 个极长上升子段的排列总数。
Solution
看到“恰好”即考虑二项式反演。
设 F_i 为将 [1,N] 划分为恰好 i 个上升段（段与段之间相邻数要严格 >）的方案数，G_i 为划分为至少 i 个上升段（段与段分界处大小关系不做要求）的方案数。所求即 F_k。
计算 G_i 是容易的：首先把 [1,N] 划分进 i 个非空集合（这是第二类斯特林数 n \brace i），由于上升段之间区分顺序，所以 \displaystyle G_i={n \brace i} i!。
如果不加思考，你就会得到一个看上去很对但其实错误的式子：
G_i = \sum_{j=i}^N \binom{j}{i} F_j \\
F_i = \sum_{j=i}^N (-1)^{j-i} \binom{j}{i} G_j
:::error[为什么这么做不对]
事实上第一个式子 G_i = \sum_{j=i}^N \binom{j}{i} F_j 组合意义就不对。
考虑此题另外一种正确的反演：记 F^\prime_i 为恰好 i 个位置满足 p_x>p_{x+1} 的方案数，G^\prime_i 为钦定 i 个位置满足 p_x>p_{x+1} 的方案数，则
G^\prime_i = \sum_{j=i}^N \binom{j}{i} F^\prime_j \\
F^\prime_i = \sum_{j=i}^N (-1)^{j-i} \binom{j}{i} G^\prime_j
这组式子正确的原因在于，恰好 j 个位置转钦定 i 个位置时，要选择 j-i 个位置不取，于是容斥系数为 \binom{j}{i}。
然而在“划分上升子序列”这个问题中，我们显然不能“选择并丢掉”若干个上升子序列，这与普通的二项式反演是有显著区别的。
:::
重新整理思路，发现在不要求段与段之间严格 > 的情况下，从任意位置切开某个极长段也是合法的。即:
G_i = \sum_{j=1}^i \binom{n-j}{i-j} F_j
解释一下，现在 p_1 \sim p_n 被划分成了 j 个极长上升段，即 n-1 个位置中已经切了 j-1 个位置；还要切 i-j 刀划分成 i 个段，所以系数是 \binom{n-j}{i-j}。
注意到组合恒等式
\binom{n}{i}\binom{i}{j}=\binom{n}{j}\binom{n-j}{i-j}
那么
G_i = \sum_{j=1}^i \frac{\binom{n}{i}\binom{i}{j}}{\binom{n}{j}} F_j \\
\frac{G_i}{\binom{n}{i}} = \sum_{j=1}^i \binom{i}{j} \frac{F_j}{\binom{n}{j}}
化为标准形式，这样便可以二项式反演了！
F_i = \sum_{j=1}^i (-1)^{i-j} \binom{n-j}{i-j} G_j
代入 k=i 与 \displaystyle G_j = {n \brace j}j! 得到
F_k = \sum_{i=1}^k (-1)^{k-i} \binom{n-i}{k-i} \cdot {n \brace i}i!
代入第二类斯特林数通项 \displaystyle {n \brace i}=\sum_{x=0}^i \frac{(-1)^{i-x} x^n}{x!(i-x)!}（可自行推导，参见 OI-wiki），得
F_k &= \sum_{i=1}^k (-1)^{k-i} \binom{n-i}{k-i} \sum_{x=0}^i (-1)^{i-x} x^n \binom{i}{x} \\
&= \sum_{x=0}^k (-1)^{k-x} x^n \ \sum_{i=x}^k \binom{n-i}{k-i} \binom{i}{x} \\
&= \sum_{x=0}^k (-1)^{k-x} x^n \ \sum_{i=x}^k \binom{n-i}{n-k} \binom{i}{x}
\end{aligned}
观察到后面是组合数上指标卷积的形式，有公式
\sum_i \binom{i}{a} \binom{n-i}{b} = \binom{n+1}{a+b+1}
:::info[证明]
考虑组合意义：从 n+1 个数里取出 a+b+1 个数。
设取的第 a+1 个数的排名为 j+1，那么左边 j 个数取 a 个数，右边 n-j 个数取 b 个数。得证。
注意与范德蒙德卷积（下指标卷积求和）区分。
:::
那么
F_k &= \sum_{x=0}^k (-1)^{k-x} x^n \binom{n+1}{n-k+x+1} \\
&= \sum_{x=0}^k (-1)^{k-x} x^n \binom{n+1}{k-x}
\end{aligned}
直接计算即可。复杂度 \mathcal O(n+k \log n)。