【题解】CF960G Bandit Blues

CF960G Bandit Blues

给定正整数 $n,A,B$，定义 $a$ 为一个排列中前缀 $\max$ 的个数，$b$ 为这个排列中后缀 $\max$ 的个数。求长度为 $n$ 的排列中，满足 $a=A,b=B$ 的排列有多少个。答案对 $998244353$ 取模。
$n \le 10^5,0\le A,B \le n$。

$\texttt{Solution}$

考虑根据最大的数 $n$ 对排列进行划分，发现对于 $n$ 及以后，前缀 $\max$ 均为 $n$，$n$ 及以前，后缀 $\max$ 均为 $n$。所以，现在如果排除 $n$，还需要有 $A-1$ 和 $B-1$ 个数字作为前缀/后缀 $\max$。

考虑前缀 $\max$，后缀同理。对于一种方案，我们可以将一个前缀 $\max$ 及其以后，直到下一个 $\max$ 之前的所有数字划分成一组，那么现在 $n$ 之前一共有 $A-1$ 组。注意组内除了最大的数字放在最左边之外，其他数字顺序不一样也是不同的方案。

观察发现其中一个组类似一个圆排列，从圆排列中最大的数的位置断开，然后成为一个序列。同时，只要所有的圆排列确定了，那么一定按照圆排列中 $\max$ 从小到大来排。

后缀 $\max$ 就是把组内最大的数字放在最右边，然后将组按照 $\max$ 从大到小排。

加上后缀的条件，除了 $n$ 这一个元素之外，其他 $n-1$ 个元素需要组成 $A-1+B-1=A+B-2$ 个圆排列，同时需要把他们分配到 $n$ 的左右两边，因此答案是：

$$\begin{bmatrix} n-1 \\ A+B-2 \end{bmatrix} \times \binom{A+B-2}{A-1}$$

其中 $\begin{bmatrix} n-1 \\ A+B-2 \end{bmatrix}$ 是第一类斯特林数。

到这里就可以解决上面的简化版了。但是我们知道，第一类斯特林数的递推是 $\mathcal{O}(n^2)$ 的，在这里无法通过，因此考虑直接求一整行/一整列的第一类斯特林数，然后拿出这个值。本人选择的是一整行的第一类斯特林数。

~~众所周知~~ 第一类斯特林数满足以下柿子：

$$x^{\overline{n}}=\sum_{i=0}^n\begin{bmatrix} n \\ i \end{bmatrix} x^i$$

可以通过归纳法证明：

$$x^{\overline{n+1}}=\Big( \sum_{i}\begin{bmatrix} n \\ i \end{bmatrix} x^i \Big)(x+n)$$

$$=\sum_{i=0}^{n+1} \Big(\begin{bmatrix} n \\ i-1 \end{bmatrix}+n\times \begin{bmatrix} n \\ i \end{bmatrix}\Big) x^i$$

$$=\sum_{i=0}^{n+1}\begin{bmatrix} n+1 \\ i \end{bmatrix} x^i$$

考虑计算 $x^{\overline{n}}$，可以倍增：

$$x^{\overline{2n}}=x^{\overline{n}}\times (x+n)^{\overline{n}}$$

设 $f(x) = x^{\overline{n}}$，那么 $(x+n)^{\overline{n}}$ 就是 $f(x+n)$。设 $f(x)$ 的 $x^i$ 项系数为 $a_i$，那么有：

$$f(x+n)=\sum_{i=0}^n a_i(x+n)^i$$

直接二项式定理拆掉之后交换一下求和符号，再拆掉二项式定理的组合数可以得到：

$$f(x+n) = \sum_{j=0}^n \dfrac{x^j}{j!} \sum_{i=j}^n a_i\times i! \times \dfrac{n^{i-j}}{(i-j)!}$$

设 $A(x)=a_x\times x!,B(x)=\dfrac{n^{x}}{x!}$，带进去可得：

$$f(x+n)=\sum_{j=0}^n \dfrac{x^j}{j!} \sum_{i=j}^n A(i) \times B(i-j)$$

$$=\sum_{j=0}^n \dfrac{x^j}{j!} \sum_{i=0}^{n-j} A(i+j) \times B(i)$$

$$=\sum_{j=0}^n \dfrac{x^j}{j!} \sum_{i=0}^{n-j} A'(n-i-j) \times B(i)$$

其中 $A'$ 是 $A$ 反转之后的序列。

后面就是一个卷积形式了，直接上一发 $\texttt{NTT}$。

然后就可以求出 $f(x+n)$，求 $f(x)f(x+n)$ 就再来一发 $\texttt{NTT}$。

时间复杂度 $T(n)=T(\frac{n}{2})+\mathcal{O}(n\log n)=\mathcal{O}(n\log n)$。