题解 P8554【心跳】（魔怔题解）

小粉兔 · 2022-09-24 22:14:00 · 题解

考虑找出合法的 a 的结构，并基于结构性质，进行去重和 \ge m 的统计。

我们考虑原排列中的每个前缀最大值都“控制”它后面的一段：也即，那一段内的元素都小于这个前缀最大值，这个控制的区间向右延伸到下一个前缀最大值前（或排列末尾）。

记原排列的前缀最大值个数为 k，也即段数为 k。删去非前缀最大值时，序列的前缀最大值个数不会改变，这也就是说，如果 p_i 不为前缀最大值，则 a_i = k。

当删去前缀最大值时，这个前缀最大值所控制的段内其他元素都将暴露在外，如果这些元素中出现了新的 x 个前缀最大值，则新序列的前缀最大值个数应为 k - 1 + x，即原排列的前缀最大值个数，去掉这个被删去的前缀最大值，再加上新出现的 x 个前缀最大值。
记这一段（包含它自己）的长度为 h，由于 x 至多为 h - 1，这说明新的前缀最大值个数将在 [k - 1, k + h - 2] 中选取。我们进一步要探讨的是，如果仅知道每一段的长度，这 [k - 1, k + h - 2] 中的 h 个数是否都能取到；换言之，给定每一段的长度 h_{1 \sim k}，对于每个前缀最大值的每个 a_i \in [k - 1, k + h - 2] 的方案，是否都能构造一个排列 p 使其恰好得到序列 a？

答案几乎是肯定的：除了在第一段中如果 h \ge 2 就无法取到 a_1 = k - 1 外，总能构造一个排列 p 使其恰好得到序列 a。
我们可以感性证明一下这个结论。注意，在原排列中，“当删去前缀最大值时，这个前缀最大值所控制的段内其他元素都将暴露在外”。只要我们可以自由控制这 h - 1 个元素暴露在外后，恰好出现的前缀最大值的数量（即在 [0, h - 1] 中任取），就能达到根据每段长度和每个 a_i 反向构造原排列的目的。
对于所有段，可以发现，总是可以排列段内其他元素的相对顺序（段内所有元素都大于上一段的最大值），达到恰好新出现 [1, h - 1] 个前缀最大值。
要达到恰好新出现 0 个前缀最大值，即其他元素全部被前一段的最大值隐藏，前提是“存在前一段”或 h = 1，即当第一段的 h \ge 2 时，不可能取到 a_1 = k - 1。

我们恰恰是要对序列 a 进行计数，所以前述结论（对 a 的合法性判定）将提供莫大的帮助。但是我们仍需要对序列 a 进行去重，因为可能存在不同的段分布情况对应到相同的序列 a 的情况：

注意它们的段分布情况不同，但是对应的序列 a 相同，所以不能通过段分布情况对所有可能的序列 a 直接进行分类。

为了进一步考虑对不同的段分布情况的序列 a 去重，我们基于序列 a 引入一个新序列称作序列 b ：
已知序列 a 对应的原排列的段数为 k，此时令 b 为 a 中每个元素减去 k 构成的序列，则原排列中不为前缀最大值的位置在序列 b 中对应的值为 0。

考察序列 b 中的那些前缀最大值位置，我们知道它们的取值为 [-1, h - 2]，其中 h 为这一段的长度。为了给序列 a 去重，我们不先确定段分布情况，而是从序列 b 的每个元素的具体数值入手。如果确定了序列 b 中的某个段首位置的值，即确定了 b_i = v，则根据前文可知这一段的长度 h 满足 h \ge v + 2。所以，如果按段首的具体数值分类，每一段在序列 b 中必然呈现如下形式：

以此类推……

回顾序列 b 的定义，可知只要确定了 (b, k) 就可以反向构造出唯一的 a。当然，这里的 (b, k) 必须是合法的。使用上文列举的段结构，我们可以清晰地认识附加了段分布信息的序列 b 的结构，对其进行计数也是很容易的：

我们可以把每一段看作 [-1], [0, 0], [1, 0, 0], [2, 0, 0, 0], \ldots 之一与若干个 0 拼接而成。
记段的组合类为 \mathcal{S}，则 \displaystyle \operatorname{OGF}(\mathcal{S}) = \frac{x}{1 - x} \cdot \frac{1}{1 - x}。
注意第一段不能以 [-1, 0] 为前缀，只能是 [-1] 或以其他数开头，所以记第一段的组合类为 \mathcal{S}_1 时有 \displaystyle \operatorname{OGF}(\mathcal{S}_1) = x + \frac{x^2}{1 - x} \cdot \frac{1}{1 - x}。
那么附加了段分布信息的序列 b 的组合类就是 \mathcal{S}_1 \times \operatorname{SEQ}(\mathcal{S})，有 OGF \displaystyle \frac{x + \dfrac{x^2}{1 - x} \cdot \dfrac{1}{1 - x}}{1 - \dfrac{x}{1 - x} \cdot \dfrac{1}{1 - x}}。

但是，我们需要计数的并不是附加上段结构信息的序列 b ，而是序列 a。注意：

相同的序列 b，如果有不同的 k（即段数），当然会对应到不同的序列 a 上。
相同的序列 b，如果有不同的段结构信息，但段数 k 相同，也会对应到相同的序列 a 上。

即，从序列 b 的角度来看，我们要计数的是带段数信息的不同的序列 b 个数。即，不同的序列 b 依然算作不同，但相同的序列 b，如果段数不同也算作不同，段数相同则算作相同。举个例子：

前两个 \langle b, k \rangle 需要被视为同一类，但第三个 \langle b, k \rangle 有着不同的 k，需要分开计数。

注意，这里默认了不同的序列 b 必然对应不同的序列 a，这个结论是正确的，然而并不显然（初看时，无法否认两个相差为常数的序列 b 由于段数 k 不同而对应到相同的序列 a 上的可能性）。

通过上述例子，容易观察到出现重复的 \langle b, k \rangle 的原因：在序列 b 中有 [0, 0] 段的存在，更一般地，有形如 [0, 0] 后跟若干个 0 的段的存在。它们的分布方式不同，但数量相同时，就会导致重复统计。如果禁止这样的段的出现呢？

如果强制不能出现“形如 [0, 0] 后跟若干个 0 的段”，即是每一段的首位都非零，可以直接根据序列 b 本身的值唯一确定段分布信息，故也确定了段数。这就是说，直接将 [-1], [1, 0, 0], [2, 0, 0, 0], \ldots 之一与若干个 0 拼接而成的段进行不限数量的有序拼接（\operatorname{SEQ}）即可不重不漏地枚举到所有序列 b。
翻译成符号化方法的语言即是，\displaystyle \operatorname{OGF}(\mathcal{S}) = \left( \frac{x}{1 - x} - x^2 \right) \cdot \frac{1}{1 - x} 和 \displaystyle \operatorname{OGF}(\mathcal{S}_1) = x + \frac{x^3}{1 - x} \cdot \frac{1}{1 - x}。
而不允许出现 0 开头的段的序列 b 的组合类即是 \mathcal{S}_1 \times \operatorname{SEQ}(\mathcal{S})，有 OGF \displaystyle \frac{x + \dfrac{x^3}{1 - x} \cdot \dfrac{1}{1 - x}}{1 - \left( \dfrac{x}{1 - x} - x^2 \right) \cdot \dfrac{1}{1 - x}}。

但是如果考虑上首位为 0 的段，我们应该如何把首位为 0 的段按出现次数进行去重呢？有关键性质：

不带段分布信息地给定一个合法序列 b，它能对应的合法 k 必须是一个区间。感性理解：
区间必须有端点 k \in [l, r]，我们可以构造性地指出端点和中间所有数都能被 k 取到。
显然每个非零数都必须在不同的段中，不妨先粗暴地把每个非零数与其后面的 0 连续段划分为同一段。序列 b 以 0 或 -1 开头时进行一些特别处理。举一些例子：
- 将 b = [2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0] 划分为 [\underline{2, 0, 0, 0, 0, 0, 0, 0}\ ,\ \underline{1, 0, 0, 0}\ ,\ \underline{-1, 0, 0, 0}\ ,\ \underline{1, 0, 0}]。
- 将 b = [0, 0, 0, 0, 0, 2, 0, 0, 0, -1, 0, 1, 0, 0, 0, -1] 划分为 [\underline{0, 0, 0, 0, 0}\ ,\ \underline{2, 0, 0, 0}\ ,\ \underline{-1, 0}\ ,\ \underline{1, 0, 0, 0}\ ,\ \underline{-1}]。
- 将 b = [-1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0] 划分为 [\underline{-1}\ ,\ \underline{0, 0, 0, 0, 0}\ ,\ \underline{1, 0, 0, 0, 0, 0}\ ,\ \underline{-1, 0, 0, 0}]。
总的来说，即是保证每一段在合法的前提下尽量长。可以看出，这种划分唯一且一定是合法的，否则就不存在任何合法划分了。这样导出的段分布一定是段数最少的，此时即为 k = l，取到区间的左端点。
对于右端点，考虑划分段数最多的方式。如果这一段的首元素为 v，则段必须至少长度为 v + 2，但是如果在前一种划分方式中段长为 h，即是说在段的末尾超出了 h - (v + 2) 个 0。这写多余的 0，为了使段数尽量多，可以两个两个结合成段，即产生 \left\lfloor \dfrac{h - (v + 2)}{2} \right\rfloor 个新的段，按相同例子：
- 将 b = [2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0] 划分为 [\underline{2, 0, 0, 0}\ ,\ \underline{0, 0}\ ,\ \underline{0, 0}\ ,\ \underline{1, 0, 0, 0}\ ,\ \underline{-1, 0}\ ,\ \underline{0, 0}\ ,\ \underline{1, 0, 0}]，k 增加了 3。
- 将 b = [0, 0, 0, 0, 0, 2, 0, 0, 0, -1, 0, 1, 0, 0, 0, -1] 划分为 [\underline{0, 0, 0}\ ,\ \underline{0, 0}\ ,\ \underline{2, 0, 0, 0}\ ,\ \underline{-1, 0}\ ,\ \underline{1, 0, 0, 0}\ ,\ \underline{-1}]，k 增加了 1。
- 将 b = [-1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 0] 划分为 [\underline{-1}\ ,\ \underline{0, 0, 0}\ ,\ \underline{0, 0}\ ,\ \underline{1, 0, 0, 0}\ ,\ \underline{0, 0}\ ,\ \underline{-1, 0}\ ,\ \underline{0, 0}]，k 增加了 3。
这种满足段数尽量多的划分不一定唯一，如果存在 h - (v + 2) 为奇数且 \ge 3，则可以有多种具体的段分布方式。相比 k 尽量少的划分，k 一般会增加，但也可能无法增加，即可能存在每一段都出现了 h - (v + 2) \le 1 的情况。
由于划分段数最多是基于划分段数最少的方法进一步划分而成，显然中间的每个数都能被 k 取到，只需进行不完全的划分即可。

既然已知不带附加信息的合法序列 b 可以对应一个区间中的 k，再考虑到 m 的需求——由于 b 的最小值为 0 或 -1，要求 a 的值域在 [m, n] 中，即是要求 k 需要大于某个值（这里根据最小值是否取到 -1 会有一些偏差，后文中会展开细节），结合这两点我们考虑直接附带记录 k 的信息。

即，我们试图求出，k 恰好为某个值的数值不同的序列 b（不带附加信息）的个数。通过区间的性质，我们考虑从左右端点切入。如果可以求出：

对应到的 k 区间的左端点恰好为 l 的序列 b 的个数，记作 f(n, l)。
对应到的 k 区间的右端点恰好为 r 的序列 b 的个数，记作 g(n, r)。

如果记 h(n, k) 表示能够取到 k 的序列 b 的个数，则有 \displaystyle h(n, k) = \sum_{l = 1}^{k} f(n, l) - \sum_{r = 1}^{k - 1} g(n, r)。

现在只考虑求 f 和 g。使用二元生成函数，将 l 和 r 作为 y 的次数引入信息。下面继续沿用前文中符号化方法的记号。

对于 f，即 y 的次数为左端点，由于每一段不再分裂：

有 \displaystyle \operatorname{OGF}(\mathcal{S}) = y \cdot \left[ \left( \frac{x}{1 - x} - x^2 \right) \cdot \frac{1}{1 - x} \right]。
对于首（两）段的特殊处理，有 \displaystyle \operatorname{OGF}(\mathcal{S}_1) = y \cdot \left( x + x \cdot y \cdot \frac{x^2}{1 - x} + \frac{x^2}{1 - x} \cdot \frac{1}{1 - x} \right)。这是因为首段可以以 0, 1, 2, \ldots 开头，而 -1 开头时，要么不能往后接 0 了，要么后面的 0 至少接两个，并独立成段。
最后，有 \mathcal F = \mathcal{S}_1 \times \operatorname{SEQ}(\mathcal{S})。对于 OGF 有
\begin{aligned} F(x, y) = \operatorname{OGF}(\mathcal{F}) &= \frac{\operatorname{OGF}(\mathcal{S}_1)}{1 - \operatorname{OGF}(\mathcal{S})} \\ &= \frac{y \cdot \left( x + x \cdot y \cdot \dfrac{x^2}{1 - x} + \dfrac{x^2}{1 - x} \cdot \dfrac{1}{1 - x} \right)}{1 - y \cdot \left[ \left( \dfrac{x}{1 - x} - x^2 \right) \cdot \dfrac{1}{1 - x} \right]} \\ \text{(WolframAlpha or Mathematica)\qquad} &= \frac{x y - x^2 y + x^3 y + x^3 y^2 - x^4 y^2}{1 - (2 x - x^2 + y \cdot (x - x^2 + x^3))} \text{.} \end{aligned}

对于 g，即 y 的次数为右端点，考虑每一段额外多出的 0 的个数为 w 时会产生 \lfloor w / 2 \rfloor 个新段：

有 \displaystyle \operatorname{OGF}(\mathcal{S}) = \left[ y \cdot (1 + x) \cdot \left( \frac{x}{1 - x} - x^2 \right) \right] \cdot \frac{1}{1 - y \cdot x^2}。此处相当于以基本的 \displaystyle \frac{x}{1 - x} - x^2 为基础，先乘上 (1 + x) 表示多出奇数个 0 与偶数无异，然后乘上 y 表示这一段本身的贡献，后面乘上 \operatorname{SEQ}(y \cdot x^2) 表示每两个 0 单独成段。
对于首（若干）段的特殊处理，有 \displaystyle \operatorname{OGF}(\mathcal{S}_1) = y \cdot x + \left[ y \cdot (1 + x) \cdot \left( x \cdot y \cdot x^2 + \frac{x^2}{1 - x} \right) \right] \cdot \frac{1}{1 - y \cdot x^2}。其中在外的 y \cdot x 对应首段为 -1 并不接任何 0 的情况，内部的 x \cdot y \cdot x^2 对应首（两）段为 [-1]、[0, 0] 的情况，它们也需要乘 (1 + x) 和 \displaystyle \frac{1}{1 - y \cdot x^2}。
最后，有 \mathcal G = \mathcal{S}_1 \times \operatorname{SEQ}(\mathcal{S})。对于 OGF 有
\begin{aligned} G(x, y) = \operatorname{OGF}(\mathcal{G}) &= \frac{\operatorname{OGF}(\mathcal{S}_1)}{1 - \operatorname{OGF}(\mathcal{S})} \\ &= \frac{y \cdot x + \left[ y \cdot (1 + x) \cdot \left( x \cdot y \cdot x^2 + \dfrac{x^2}{1 - x} \right) \right] \cdot \dfrac{1}{1 - y \cdot x^2}}{1 - \left[ y \cdot (1 + x) \cdot \left( \dfrac{x}{1 - x} - x^2 \right) \right] \cdot \dfrac{1}{1 - y \cdot x^2}} \\ \text{(WolframAlpha or Mathematica)\qquad} &= \frac{x y + x^3 y + x^4 y^2 - x^5 y^2}{1 - (x + y \cdot (x + x^2 - x^3 + x^4))} \text{.} \end{aligned}

接下来，根据 \displaystyle h(n, k) = \sum_{l = 1}^{k} f(n, l) - \sum_{r = 1}^{k - 1} g(n, r)，我们有 \displaystyle H(x, y) = \operatorname{OGF}(\mathcal{H}) = \frac{1}{1 - y} \cdot F(x, y) - \frac{y}{1 - y} \cdot G(x, y)。

根据 F(x, y) 和 G(x, y) 的二元有理分式，容易在 \mathcal{O}(n^2) 计算它们在 \langle n, n \rangle 次项处的截断，并进一步得到 h(n, k) 的每个值。

仍要注意，直接计算 \displaystyle \sum_{k = m}^{n} h(n, k) 并不能得到答案，这是因为多统计了当 k = m 时，序列 b 中有 -1 的存在导致序列 a 的对应位置 = m - 1 < m。改为直接计算 \displaystyle \sum_{k = m + 1}^{n} h(n, k) 也不能得到答案，这是因为当 k = m 时，可能仍有一些不存在 -1 的序列 b 是满足条件的但未被统计到。所以我们只需针对 k = m 且序列 b 中不存在 -1 的情况处理。再推一遍生成函数式子，此时强制不能有 -1 的段出现：

在记号上，将禁止 -1 的相关对象加个星号。类似地，我们要求 F^{{\ast}}(x, y) 对应左端点、以及 G^{{\ast}}(x, y) 对应右端点。
对于 F^{{\ast}}(x, y)，有 \displaystyle \operatorname{OGF}(\mathcal{S}) = y \cdot \frac{x^3}{1 - x} \cdot \frac{1}{1 - x} 和 \displaystyle \operatorname{OGF}(\mathcal{S}_1) = y \cdot \frac{x^2}{1 - x} \cdot \frac{1}{1 - x}。计算可得
F^{{\ast}}(x, y) = \frac{\operatorname{OGF}(\mathcal{S}_1)}{1 - \operatorname{OGF}(\mathcal{S})} = \cdots = \frac{x^2 y}{1 - (2 x - x^2 + y \cdot (x^3))} \text{.}
对于 G^{{\ast}}(x, y)，有 \displaystyle \operatorname{OGF}(\mathcal{S}) = \left[ y \cdot (1 + x) \cdot \frac{x^3}{1 - x} \right] \cdot \frac{1}{1 - y \cdot x^2} 和 \displaystyle \operatorname{OGF}(\mathcal{S}_1) = \left[ y \cdot (1 + x) \cdot \frac{x^2}{1 - x} \right] \cdot \frac{1}{1 - y \cdot x^2}。计算可得
G^{{\ast}}(x, y) = \frac{\operatorname{OGF}(\mathcal{S}_1)}{1 - \operatorname{OGF}(\mathcal{S})} = \cdots = \frac{x^2 y + x^3 y}{1 - (x + y \cdot (x^2 + x^4))} \text{.}

那么，类似地，我们有 \displaystyle H^{{\ast}}(x, y) = \operatorname{OGF}(\mathcal{H}^{{\ast}}) = \frac{1}{1 - y} \cdot F^{{\ast}}(x, y) - \frac{y}{1 - y} \cdot G^{{\ast}}(x, y)。

答案即为 \displaystyle \sum_{k = m + 1}^{n} h(n, k) + h^{{\ast}}(n, m)。至此，本题在 \mathcal{O}(n^2) 复杂度内得到解决。

为了追求更好的时间复杂度，注意到答案为

\Big( \big[ x^n y^n \big] - \big[ x^n y^m \big] \Big) \frac{1}{1 - y} \left( \frac{1}{1 - y} \cdot F(x, y) - \frac{y}{1 - y} \cdot G(x, y) \right) + \big[ x^n y^m \big] \left( \frac{1}{1 - y} \cdot F^{{\ast}}(x, y) - \frac{y}{1 - y} \cdot G^{{\ast}}(x, y) \right) \text{,}

再结合这一事实——对关于 x 的一元多项式 P(x), Q(x) 满足 Q(0) \ne 1，有

\big[ y^m \big] \frac{1}{1 - (Q(x) + y \cdot P(x))} = {\left( \frac{P(x)}{1 - Q(x)} \right)}^m \frac{1}{1 - Q(x)} \text{.} \tag{3}

这启发我们对答案中的二元有理分式进行部分分式分解，得到分母中 y 最高次数为 1 的部分分式。

对 \displaystyle \frac{1}{{(1 - y)}^2} \cdot F(x, y)、\displaystyle \frac{y}{{(1 - y)}^2} \cdot G(x, y)、\displaystyle \frac{1}{1 - y} \cdot F^{{\ast}}(x, y)、以及 \displaystyle \frac{y}{1 - y} \cdot G^{{\ast}}(x, y) 分别进行以 y 为主元的部分分式分解（借助 Mathematica）：

\begin{aligned} \frac{1}{{(1 - y)}^2} \cdot F(x, y) &= x y \cdot \bigg[ \frac{1}{{(1 - y)}^2} \cdot \frac{1 - x + 2 x^2 - x^3}{1 - (3 x - 2 x^2 + x^3)} \\ & \qquad {} - \frac{1}{1 - y} \cdot \frac{x - x^2 + x^4}{1 - (6 x - 13 x^2 + 14 x^3 - 10 x^4 + 4 x^5 - x^6)} \\ & \qquad {} + \frac{1}{1 - (2 x - x^2 + y \cdot (x - x^2 + x^3))} \cdot \frac{x^2 - 2 x^3 + 2 x^4 - x^6 + x^7}{1 - (6 x - 13 x^2 + 14 x^3 - 10 x^4 + 4 x^5 - x^6)} \bigg] \text{.} \\ \frac{y}{{(1 - y)}^2} \cdot G(x, y) &= x y^2 \cdot \bigg[ \frac{1}{{(1 - y)}^2} \cdot \frac{1 - x + 2 x^2 - x^3}{1 - (3 x - 2 x^2 + x^3)} \\ & \qquad {} - \frac{1}{1 - y} \cdot \frac{x + x^3 - x^4 + x^5}{1 - (5 x - 7 x^2 + x^3 + 4 x^4 - 6 x^5 + 3 x^6 - x^7)} \\ & \qquad {} + \frac{1}{1 - (x + y \cdot (x + x^2 - x^3 + x^4))} \cdot \frac{x^2 + x^3 + x^5 - x^6 + 3 x^7 - 2 x^8 + x^9}{1 - (5 x - 7 x^2 + x^3 + 4 x^4 - 6 x^5 + 3 x^6 - x^7)} \bigg] \text{.} \\ \frac{1}{1 - y} \cdot F^{{\ast}}(x, y) &= x^2 y \cdot \bigg[ \frac{1}{1 - y} \cdot \frac{1}{1 - (2 x - x^2 + x^3)} \\ & \qquad {} - \frac{1}{1 - (2 x - x^2 + y \cdot (x^3))} \cdot \frac{x^3}{1 - (2 x - x^2 + x^3)} \bigg] \text{.} \\ \frac{y}{1 - y} \cdot G^{{\ast}}(x, y) &= x^2 y^2 \cdot \bigg[ \frac{1}{1 - y} \cdot \frac{1}{1 - (2 x - x^2 + x^3)} \\ & \qquad {} - \frac{1}{1 - (x + y \cdot (x^2 + x^4))} \cdot \frac{x^2 + x^4}{1 - (2 x - x^2 + x^3)} \bigg] \text{.} \end{aligned}

基于这些结果，通过先提取 \big[ y^m \big]，转化为求常数个关于 x 的常数次多项式的常有理数次幂的乘积的 \big[ x^n \big]，此时可以使用相关多项式运算达到 \mathcal O(n \log n)。

或者结合 (3) 的形式，使用 ODE 相关技术，转化为整式递推，达到 \mathcal O(n) 的复杂度。