随笔题解 Pb. 9

yukicoder contest 426 G. Sum of Subarray of Subsequence of…

注意：本题解的记号可能与原题面存在出入。

给你一个长度为 $N$ 的序列 $A$ 和一个长度为 $M$ 的字符串 $S$。$S$ 只包含 $\texttt{a}$ 和 $\texttt{s}$ 两种字符。

设 $a$ 为一序列。如下定义一系列函数 $f_0, f_1, \dots, f_M$：

1. $f_0(a)$ 为 $a$ 中所有元素的和
2. 对于 $i \gt 0$
   1. 如果 $S_i = \texttt{a}$，$f_i(a)$ 为 $a$ 的所有 子区间（连续） 上的 $f_{i - 1}$ 的函数值的和
   2. 如果 $S_i = \texttt{a}$，$f_i(s)$ 为 $a$ 的所有 子序列（不一定连续） 上的 $f_{i - 1}$ 的函数值的和

让你求出 $f_M(A)$。对 $998244353$ 取模。

$1 \leqslant N, M \leqslant 10^5$。$0 \leqslant A_i \lt 998244353$。

$\texttt{4s/512MiB}$。

---

不难发现，$f_i(a)$ 一定是 $a$ 中所有元素的某种带权和。

考虑设 $\lambda_i(x, y)$ 表示对于一个长度为 $x + y + 1$ 的序列 $a$，$f_i(a)$ 里 $a_{x + 1}$ 的权值。即

$$f_i(a) = \sum_{j = 1}^{|a|} \lambda_i(j - 1, |a| - j) a_j$$

至于为什么下标要写成这样，因为这样更直观：$a_{x + 1}$ 的左侧有 $x$ 个其他元素，右侧有 $y$ 个其他元素。

边界条件是

$$\lambda_0(p, q) = 1$$

再令 $\lambda_i$ 的 OGF 为

$$\Lambda_i(x, y) = \sum_{p \geqslant 0} \sum_{q \geqslant 0} \lambda_i(p, q) x^p y^q$$

如果 $S_i = \texttt{a}$

$$\lambda_i(p, q) = \sum_{r = 0}^p \sum_{s = 0}^q \lambda_{i - 1}(r, s)$$ $$\begin{aligned} \Lambda_i(x, y) =& \sum_{p \geqslant 0} \sum_{q \geqslant 0} \lambda_i(p, q) x^p y^q \\ =& \sum_{p \geqslant 0} \sum_{q \geqslant 0} \sum_{r = 0}^p \sum_{s = 0}^q \lambda_{i - 1}(r, s) x^p y^q \\ =& \sum_{r \geqslant 0} \sum_{s \geqslant 0} \lambda_{i - 1}(r, s) \sum_{p \geqslant r} \sum_{q \geqslant s} x^p y^q \\ =& \sum_{r \geqslant 0} \sum_{s \geqslant 0} \lambda_{i - 1}(r, s) \frac{x^r y^s}{(1 - x) (1 - y)} \\ =& \frac{\Lambda_{i - 1}(x, y)}{(1 - x) (1 - y)} \end{aligned}$$

如果 $S_i = \texttt{s}$

$$\lambda_i(p, q) = \sum_{r = 0}^p \sum_{s = 0}^q \binom{p}{r} \binom{q}{s} \lambda_{i - 1}(r, s)$$ $$\begin{aligned} \Lambda_i(x, y) =& \sum_{p \geqslant 0} \sum_{q \geqslant 0} \lambda_i(p, q) x^p y^q \\ =& \sum_{p \geqslant 0} \sum_{q \geqslant 0} \sum_{r = 0}^p \sum_{s = 0}^q \binom{p}{r} \binom{q}{s} \lambda_{i - 1}(r, s) x^p y^q \\ =& \sum_{r \geqslant 0} \sum_{s \geqslant 0} \lambda_{i - 1}(r, s) \sum_{p \geqslant r} \sum_{q \geqslant s} \binom{p}{r} \binom{q}{s} x^p y^q \\ =& \sum_{r \geqslant 0} \sum_{s \geqslant 0} \lambda_{i - 1}(r, s) \frac{x^r y^s}{(1 - x)^{r + 1} (1 - y)^{s + 1}} \\ =& \frac{\Lambda_{i - 1}(x / (1 - x), y / (1 - y))}{(1 - x) (1 - y)} \end{aligned}$$

我们想要求的是 $\Lambda_M(x, y)$ 的系数。

考虑从 $\Lambda_i(\tilde x, \tilde y)$ 到 $\Lambda_{i - 1}(\tilde x, \tilde y)$ 的过程。这里 $\tilde x$ 和 $\tilde y$ 表示到这一步的时候的实际的自变量。

首先会在柿子里面留下一个

$$\frac{1}{(1 - \tilde x) (1 - \tilde y)}$$

然后如果 $S_i = \texttt{s}$，两个自变量会分别变成

$$\frac{\tilde x}{1 - \tilde x}, \frac{\tilde y}{1 - \tilde y}$$

手玩以下可以发现，上面这个过程如果说进行了 $l$ 次，两个自变量会变成

$$\frac{x}{1 - lx}, \frac{y}{1 - ly}$$

这里的 $x, y$ 表示一开始代进 $\Lambda_M$ 的两个自变量。

然后每次再柿子里留下的那一部分会变成

$$\frac{1 - lx}{1 - (l + 1) x}, \frac{1 - ly}{1 - (l + 1) y}$$

并且到 $\Lambda_0$ 还没完。所以你可以想象后面还有一个 $\Lambda_{-1} \equiv 1$。

那么结论就是，存在 $r_0, r_1, \dots, r_{M + 1}$ 使得

$$\Lambda_M(x, y) = \prod_{j = 0}^{M + 1} (1 - jx)^{r_j} (1 - jy)^{r_j}$$

最后的答案就是

$$\begin{aligned} & \sum_{i = 1}^N [x^{i - 1} y^{n - i}] \Lambda_M(x, y) A_i \\ =& \sum_{i = 1}^N \left( [x^{i - 1}] \prod_{j = 0}^{M + 1} (1 - jx)^{r_j} \right) \left( [y^{n - i}] \prod_{j = 0}^{M + 1} (1 - jy)^{r_j} \right) A_i \end{aligned}$$

然后你会发现 $x$ 和 $y$ 的部分完全分开了。而且两部分其实长得一模一样。

中间那两坨我们可以用分治 + NTT 的技巧求解。时间复杂度 $\Theta(N \log_2^2 N)$。

评测记录