排列计数[luogu5825]

题意

对于所有长度为 $n$ 的排列 $p$，求有 $k$ 个 $i$ 满足 $p_i<p_{i+1}$ 的方案数。

对于所有的 $k$ 都要算。

$n\leq 2\times 10^5$

题解

有一个较为简单的DP，顺次考虑将 $i$ 插入进排列，转移很简单，时间复杂度 $O(n^2)$。

然后你发现做不下去了，考虑至少容斥，设 $F_i$ 为答案，$G_k$ 为至少有 $k$ 个 $i$ 满足条件的方案数。那么最后二项式反演+ntt即可算出 $F$。

考虑钦定了 $k$ 个位置的小于号，然后将连续的小于号的搞成一个连续段，那么将有 $n-k$ 个连续段，且如果知道了段内的数组，那么段内的顺序也是确定的。

假设段的长度为 $x_1,x_2\cdots,x_m$，那么一共有 $\frac{n!}{\prod_{i=1}^m x_i}$ 个贡献，要求满足 $x_i\geq 1$

考虑用生成函数解决：

$$G _ k=[x ^ n]((\sum _ {i=0} \frac{x ^ i}{i!})-1) ^ {n-k}=[x ^ n] (e ^ x-1) ^ {n-k}$$

设 $m=n-k$，则：

$$x^n^m=\sum_{i=0}^m[x^n]e^{xi}(-1)^{m-i}\binom{m}{i}=\sum_{i=0}^m\frac{i^n}{n!}(-1)^{m-i}\binom{m}{i}$$

搞一个ntt就好了。

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

程序

懒得搞了，反正很简单。