自动搬运

查看原文

来自洛谷，原作者为

	Karry5307 兄弟会背叛你，女人会离开你，金钱会诱惑你，生活会刁难你，只有数学不会，不会就是不会，怎么学都不会

搬运于2025-08-24 22:28:26，当前版本为作者最后更新于2021-01-26 18:10:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

$T$ 组询问，求有多少个长度为 $n$ 的排列 $\pi$ 满足如下条件：

• $\pi_1<\pi_2$

• $\pi_{n-1}>\pi_{n}$

• 恰好存在 $k$ 个位置 $i(2\le i\le n-1)$ 满足 $\pi_{i-1}<\pi_{i}$ 且 $\pi_{i}>\pi_{i+1}$。

答案对 $998244353$ 取模。

$\texttt{Data Range:}1\leq T\leq 2\times 10^5,3\leq n\leq r\leq 2\times 10^5,\max(1,\lfloor\frac{n-1}{2}\rfloor-10)\leq k\leq \lfloor\frac{n-1}{2}\rfloor$

前言

题目名来源请右转这里

Rikka 可爱！

题解

首先考虑暴力 DP。由于我们只需要关心极大值有多少个，只需要看有多少个极长单调子段。讨论一下第一个和最后一个位置所处子段的单调性就可以设四个东西来：

• 设 $f_{n,k}$ 表示长度为 $n$ 并满足 $\pi_1<\pi_2,\pi_{n-1}>\pi_n$ 且有 $k$ 个极大值的排列个数。

• 设 $g_{n,k}$ 表示长度为 $n$ 并满足 $\pi_1>\pi_2,\pi_{n-1}>\pi_n$ 且有 $k$ 个极大值的排列个数。

• 设 $g^{\prime}_{n,k}$ 表示长度为 $n$ 并满足 $\pi_1<\pi_2,\pi_{n-1}<\pi_n$ 且有 $k$ 个极大值的排列个数。

• 设 $h_{n,k}$ 表示长度为 $n$ 并满足 $\pi_1>\pi_2,\pi_{n-1}<\pi_n$ 且有 $k$ 个极大值的排列个数。

这里排列的第一个和最后一个位置并不算极大值，下面的图中，左上表示 $f_{n,k}$，右上表示 $g_{n,k}$，左下表示 $g^{\prime}_{n,k}$，右下表示 $h_{n,k}$，红圈圈出来的表示计入的极大值，必须要恰有 $k$ 个，一个极长单调子段中只标出了首尾元素。

同时有两个性质：如果 $(\pi_1,\cdots,\pi_n)$ 是被计入 $g$ 的，那么 $(\pi_n,\cdots,\pi_{1})$ 则会被计入 $g^{\prime}$，也即 $g_{n,k}=g^{\prime}_{n,k}$。如果 $(\pi_1,\cdots,\pi_n)$ 是被计入 $h$ 的，那么 $(n-\pi_1+1,\cdots,n-\pi_n+1)$ 则会被计入 $f$，但是要多统计一个极大值，也即 $h_{n,k}=f_{n,k+1}$。

这样只需要对 $f_{n,k}$ 和 $g_{n,k}$ 进行 DP。考虑将 $n$ 插到长度为 $n-1$ 的排列中。注意到插到极大值两边不会造成 $k$ 的增加，别的地方均可以造成极大值的增加（这也是为什么首尾不计入极大值的原因），于是可以列出如下式子：

$$\begin{cases}f_{i,j}=2jf_{i-1,j}+(i-2j)f_{i-1,j-1}+g_{i-1,j-1}+g^{\prime}_{i-1,j-1}\\g_{i,j}=2jg_{i-1,j}+(i-2j-1)g_{i-1,j-1}+g_{i-1,j}+f_{i-1,j}+h_{i-1,j-1}\end{cases} $$

第一个式子中右边分别表示插在极大值两侧，不插在极大值两侧，插在满足 $g$ 的排列的前两个位置之间，满足 $g^{\prime}$ 的后两个位置之间。第二个式子中右边分别表示插在极大值两侧，不插在极大值两侧，插在满足 $g$ 的排列的最左边，满足 $f$ 的最左边以及满足 $h$ 的前两个位置之间。

但是根据之前的两个性质可以简化一下这个式子：

$$\begin{cases}f_{i,j}=2jf_{i-1,j}+(i-2j)f_{i-1,j-1}+2g_{i-1,j-1}\\g_{i,j}=(2j+1)g_{i-1,j}+(i-2j-1)g_{i-1,j-1}+2f_{i-1,j}\end{cases} $$

注意到这两个式子长得很像，所以可以合并成一个。设 $f^{\prime}_{i,2j}=f_{i,j},f^{\prime}_{i,2j+1}=g_{i,j}$，那么很明显可以合并成这样：

$$f^{\prime}_{i,j}=jf^{\prime}_{i-1,j}+(i-j)f^{\prime}_{i-1,j-2}+2f^{\prime}_{i-1,j-1} $$

$O(n^2)$ DP 即可拿到 32pts。

注意数据范围有一个 $\max(1,\lfloor\frac{n-1}{2}\rfloor-10)\leq k\leq \lfloor\frac{n-1}{2}\rfloor$，相当于是只需要你回答靠近对角线位置的值，所以看看能不能快速求出对角线上的值。

这里存在另外一个 DP。设 $f_n$ 表示长度为 $n$ 的排列中每个数交错并且 $\pi_1<\pi_2,\pi_{n-1}>\pi_n$ 的排列个数，$g_n$ 表示长度为 $i$ 的排列中每个数交错并且 $\pi_1>\pi_2,\pi_{n-1}>\pi_{n}$ 的排列个数，枚举 $n$ 放在哪里可以得到以下式子：

$$\begin{cases}f_{n}=\sum\limits_{i\text{ is odd}}\binom{n-1}{i}f_{i}f_{n-1-i}\\g_n=\sum\limits_{i\text{ is even}}\binom{n-1}{i}g_{i}f_{n-1-i}\end{cases} $$

到这一步可以 $O(n\log^2n+n(n-2k))$ 分治 FFT，然而这个做法不优秀，但本题可以通过。

钦定 $f_n$ 在 $n$ 为偶数的时候，$g_n$ 在 $n$ 为奇数的时候为 $0$，设 $F(x),G(x)$ 为 $f,g$ 的 EGF，则有

$$F^{\prime}(x)=F^2(x)+1,G^{\prime}(x)=F(x)G(x)$$

考虑解这个微分方程，鉴于讲评时的反响，这里给出具体解法。

$$\def\rd{\ \mathrm{d}} \frac{\rd F(x)}{\rd x}=F^2(x)+1\\\ \\ \frac{1}{F^2(x)+1}\rd F(x)=\rd x\\\ \\ \int \frac{1}{F^2(x)+1}\rd F(x)=\int\rd x\\\ \\ \tan^{-1}F(x)=x+C\\\ \\ F(x)=\tan (x+C) $$

可以自行检验 $C=0$，即 $F(x)=\tan x$，以及

$$\def\rd{\ \mathrm{d}} \frac{\rd G(x)}{\rd x}=G(x)\tan x\\\ \\ \frac{1}{G(x)}\rd G(x)=\tan x\rd x\\\ \\ \int \frac{1}{G(x)}\rd G(x)=\int \tan x\rd x\\\ \\ \ln\vert G(x)\vert=\ln\vert\sec x\vert+C\\\ \\ \vert G(x)\vert=C\vert\sec x\vert $$

可以自行检验 $C=1$ 且绝对值取正，所以 $G(x)=\sec x$。

于是，$f^{\prime}_{n,n}=[x^n](\tan x+\sec x)$，多项式求逆即可，然后再递推回来得到所有的 $f^{\prime}$，时间复杂度 $O(n\log n+n(n-2k))$。

代码就不放了，实在需要代码的找我。

彩蛋：