【题解】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}$

原题简化版:P4609 [FJOI2016]建筑师

考虑根据最大的数 $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)$。

添加新评论