【二项式反演 | 容斥】P14368 [JOISC 2018] 修行 / Asceticism 笔记

题意可以转换为求排列恰好有 $k - 1$ 个大于号的方案数。

看到恰好，考虑二项式反演转换，设 $g (k)$ 表示恰好 $k$ 个大于号， $f (i)$ 表示钦定 $i$ 个，则

g (k) = \sum_{i = k}^{n - 1} (- 1)^{i - k} (\binom{i}{k}) f (i)

考虑求 $f (i)$ ，钦定若干个位置间一定为大于号，相当于把排列划分成 $n - i$ 段，每段至少一个数、至多两个数，两个数间的为大于号。有大小关系的排列 DP 考虑按大小顺序插入，由于从大到小插入，因此每个数都是随便挑一段放。要控制每一段插入的数字个数很难，但是按照这样的插入方式，若有一段超过了两个数，必然有空段，即实际上没有分成 $n - i$ 段，用组合数筛选哪些段为空，容斥即可。

f (i) = \sum_{j = 1}^{n - i} (\binom{n - i}{j}) (- 1)^{n - i - j} j^{n}

时间复杂度 $O (n^{2})$ ，优化考虑继续推式子

g (k) = \sum_{i = k}^{n - 1} \sum_{j = 1}^{n - i} (- 1)^{i - k} (\binom{i}{k}) (\binom{n - i}{j}) (- 1)^{n - i - j} j^{n}

即

g (k) = \sum_{i = k}^{n - 1} \sum_{j = 1}^{n - i} (- 1)^{n - j - k} (\binom{i}{k}) (\binom{n - i}{j}) j^{n}

现在主要项只和 $j$ 有关，考虑把他变为外层循环，结合

{\begin{matrix} k \leq i \leq n - 1 \\ 1 \leq j \leq n - i \end{matrix}

可得

g (k) = \sum_{j = 1}^{n - k} (- 1)^{n - j - k} j^{n} \sum_{i = 1}^{n - j} (\binom{i}{k}) (\binom{n - i}{j})

后面的组合数求和相当于先在任意前 $i$ 个数中选 $k$ 个，再在剩下的 $n - i$ 个中选 $j$ 个，在这个分界点处插一个挡板即可，即

g (k) = \sum_{j = 1}^{n - k} (- 1)^{n - j - k} j^{n} (\binom{n + 1}{j + k + 1})

时间复杂度 $O (n)$ 。

【二项式反演 | 容斥】P14368 [JOISC 2018] 修行 / Asceticism 笔记 ​

【二项式反演 | 容斥】P14368 [JOISC 2018] 修行 / Asceticism 笔记