题解 P7289 【「EZEC-5」Chasse Neige】
Karry5307
·
·
题解
题意
- $\pi_1<\pi_2
答案对 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}
注意数据范围有一个 $\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))$。
代码就不放了，实在需要代码的找我。
彩蛋：
