自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 22:40:06，当前版本为作者最后更新于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$ 的情况：

• $p = [\underline{5, 3, 4, 1, 2}, \underline{7, 6}]$ 对应 $a = [\underline{3, 2, 2, 2, 2}, \underline{2, 2}]$。
• $p = [\underline{3, 1, 2}, \underline{7, 6, 4, 5}]$ 对应 $a = [\underline{3, 2, 2}, \underline{2, 2, 2, 2}]$。
• 注意它们的段分布情况不同，但是对应的序列 $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$ 中必然呈现如下形式：

• $[-1]$ 后跟零个或更多个 $0$。
• $[0, 0]$ 后跟零个或更多个 $0$。
• $[1, 0, 0]$ 后跟零个或更多个 $0$。
• $[2, 0, 0, 0]$ 后跟零个或更多个 $0$。
• $[3, 0, 0, 0, 0]$ 后跟零个或更多个 $0$。
• 以此类推……

回顾序列 $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$，如果段数不同也算作不同，段数相同则算作相同。举个例子：

• $p = [\underline{5, 3, 4, 1, 2}, \underline{7, 6}]$ 对应 $a = [\underline{3, 2, 2, 2, 2}, \underline{2, 2}]$ 和 $b = [\underline{1, 0, 0, 0, 0}, \underline{0, 0}]$ 与 $k = 2$。
• $p = [\underline{3, 1, 2}, \underline{7, 6, 4, 5}]$ 对应 $a = [\underline{3, 2, 2}, \underline{2, 2, 2, 2}]$ 和 $b = [\underline{1, 0, 0}, \underline{0, 0, 0, 0}]$ 与 $k = 2$。
• $p = [\underline{3, 1, 2}, \underline{5, 4}, \underline{7, 6}]$ 对应 $a = [\underline{4, 3, 3}, \underline{3, 3}, \underline{3, 3}]$ 和 $b = [\underline{1, 0, 0}, \underline{0, 0}, \underline{0, 0}]$ 与 $k = 3$。
• 前两个 $\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)$ 的复杂度。