Codeforces 1349F2.Slime and Sequences (Hard Version) 另解

为了膜拜 EI,口胡翻译一下另一个出题人的做法。
上次看的时候没动脑导致完全无法理解,问 EI 他说一年前写的全忘了(

看了这个暴力推 GF 做法之后感觉这个双射是从 GF 逆推出来的?

我们用 \(z\) 元计量序列长度,\(t\)\(t^k\) 的系数表示 \(k\) 的出现次数和。

首先为了显得自然,把序列反过来,也就是限制改为 \(k\) 的第一次出现之后有 \(k-1\) 出现过。
相当有启发意义地,我们发现这个限制的另一面就是所有 \(k-1\) 都在所有 \(k\) 的前面。
这提示我们容斥。令序列中最大值为 \(m\),枚举 \(S \subseteq \{1,2,\dots,m-1\}\) 表示对于 \(i \in S\) 强制所有 \(i\)\(i+1\) 之前出现,然后附有容斥系数 \((-1)^{|S|}\)

根据经验,这样的钦定就相当于把 \([1,m]\) 的整数划分为若干个 \([l,r]\),对所有 \(i \in [l,r-1]\) 钦定所有 \(i\) 出现在 \(i+1\) 之前,也就是 \([l,r]\) 内的数要「连续」地出现。
然后段数其实就是 \(m-|S|\),容斥系数也就可以看做每个段尾以外的所有元素都附有一个 \(-1\) 的因子。
我们又要同时计数每种元素的出现次数,那么若统计 \(k\),相当于给 \([1,k]\) 的每一个元素都附有一个因子 \(t\) 用来刻画元素大小。
而不同段之间我们可以用 EGF 将其位置混合。

那么我们应该统计三个阶段:完整地全部元素都附有 \(t\)(完全在需要统计出现次数的 \(k\) 之前)的段;包含最后一个 \(t\) 的终止段;不包含 \(t\) 的段。

对于第一个阶段,一种元素的贡献有至少一个 \(z\) 和恰好一个 \(t\),即 \[ \def\e{ {\rm e} } \def\d{ {\rm d} } \frac{tz}{1-z} \]

然后将此段内的所有元素混合,除去最后一个每一个都附有 \(-1\),且段内非空。那么一段的 OGF 就是 \[ \begin{aligned} L(z,t) &= 1-\frac 1{ 1+\frac{tz}{1-z} } \\ &= \frac{tz}{1-(1-t)z} \\ &= t\sum\limits_{i\ge 0} (1-t)^i z^{i+1} \end{aligned} \]

由于不同段之间的位置混合是 EGF,我们考虑其 EGF \[ \begin{aligned} \widehat L(z,t) &= t\sum\limits_{i\ge 0} (1-t)^i \frac{ z^{i+1} }{(i+1)!} \\ &= \frac t{1-t} \sum\limits_{i\ge 0} \frac{ (z(1-t))^{i+1} }{(i+1)!} \\ &= \frac t{1-t} (\e^{z(1-t)}-1) \end{aligned} \]

对于第二个阶段,一个终止段应当以若干个附有 \(-t\) 的元素、一个附有 \(t\) 且附有长度的元素、若干个只附有 \(-1\) 的元素组成。
也即 \[ \begin{aligned} U(z,t) &= \frac1{ 1+\frac{tz}{1-z} } \left(\left(z\frac{\d}{\d z}\right)\frac{tz}{1-z}\right) \frac 1{ 1+\frac z{1-z} } \\ &= \frac1{ 1+\frac{tz}{1-z} } \frac{tz}{(1-z)^2} \frac 1{ 1+\frac z{1-z} } \\ &= \frac{tz}{1-(1-t)z} \\ &= L(z,t) \\ \widehat U(z,t) &= \widehat L(z,t) \end{aligned} \]

对于第三阶段,注意到直接将 \(t=1\) 代入先前得出的 \(\widehat L(z,t)\) 是无意义的。但是注意到 \(L(z,1)=z\) 所以 \(\widehat L(z,1)=z\)

接下来组合三者,则答案的 EGF 就是 \[ \frac1{1-\widehat L(z,t)} \widehat U(z,t) \frac1{1-\widehat L(z,1)} = \frac{t(\e^{z(1-t)}-1)}{(1-z)(1-t\e^{z(1-t)})} \]

注意到 \[ \begin{aligned} & \quad \; \left([z^n] \frac{t(\e^{z(1-t)}-1)}{(1-z)(1-t\e^{z(1-t)})}\right) + 1 \\ &= [z^n] \left(\frac{t(\e^{z(1-t)}-1)}{(1-z)(1-t\e^{z(1-t)})} + \frac 1{1-z}\right) \\ &= (1-t) [z^n] \frac1{(1-z)(1-t\e^{z(1-t)})} \end{aligned} \]

接下来作换元令 \(z = \frac u{1-t}\),则 \[ \begin{aligned} [z^n] \frac1{(1-z)(1-t\e^{z(1-t)})} = (1-t)^n [u^n] \frac1{\left(1-\frac u{1-t}\right)(1-t\e^u)} \end{aligned} \]

作分式分解,设 \[ \begin{aligned} \frac1{\left(1-\frac u{1-t}\right)(1-t\e^u)} &= (1-t)\frac1{(1-t-u)(1-t\e^u)} \\ &= (1-t)\left(\frac A{1-t-u} + \frac B{1-t\e^u}\right) \end{aligned} \]

\(A(1-t\e^u) + B(1-t-u) = 1\)
\(t = \e^{-u}\) 可得 \(B = \frac1{1-\e^{-u}-u}\)
\(t = 1-u\) 可得 \(A = \frac1{1-\e^u+u\e^u}\)
所以分解为 \[ \frac{ \e^{-u} }{(1-\e^u+u\e^u)(1-t\e^u)} + \frac1{(1-\e^u+u\e^u)(1-t-u)} \]

先考虑 \([u^n]\frac1{(1-\e^u+u\e^u)(1-t-u)}\),容易将其写作 \([u^{n+1}] \frac{P(u)}{1-t-u}\),求其 \(t\) 的前 \(n\) 项只需注意到 \[ \begin{aligned} [u^{n+1}] \frac{P(u)}{1-t-u} &= [u^{n+1}] P(u) \sum\limits_{i\ge 0} (t+u)^i \\ &= [u^{n+1}] P(u) \sum\limits_{j\ge 0} u^j \sum\limits_{i\ge j} \binom ij t^{i-j} \\ &\equiv \sum\limits_{k=0}^{n+1} p_k \sum\limits_{i=0}^n \binom{n-k+1+i}i t^i \pmod { t^{n+1} } \\ &= \sum\limits_{i=0}^n t^i \sum\limits_{k=0}^{n+1} p_k \binom{n-k+1+i}i \end{aligned} \]

可以卷积。

再来考虑 \([u^n] \frac{ \e^{-u} }{(1-\e^u+u\e^u)(1-t\e^u)}\)
为了容易用拉格朗日反演的形式刻画答案,我们设 \(F(u) = \e^u - 1\),则答案可写为 \([u^{n+1}] \frac{Q(F)}{1-t(1+F)}\)
由复合逆 \(G = F^{<-1>} = \ln(1+u)\)\[ \begin{aligned} [u^{n+1}] \frac{Q(F)}{1-t(1+F)} &= \frac1{n+1} [u^n] \left(\frac{Q(u)}{1-t(1+u)}\right)' \left(\frac u{G(u)}\right)^{n+1} \\ &= \frac1{n+1} [u^n] \left(\frac{tQ(u)}{(1-t(1+u))^2}+\frac{Q'(u)}{1-t(1+u)}\right) \left(\frac uG\right)^{n+1} \end{aligned} \]

\(H = \left(\frac uG\right)^{n+1}\),有 \[ \begin{aligned} & \quad \; [u^n] \left(\frac{tQ(u)}{(1-t(1+u))^2}+\frac{Q'(u)}{1-t(1+u)}\right) H \\ &= [u^n] \left(Q\sum\limits_{i\ge 0}(i+1) t^{i} (1+u)^i+Q'\sum\limits_{i\ge 0} t^i (1+u)^i\right) H \end{aligned} \]

然后 \[ \begin{aligned} & \quad \; [u^n t^k] \left(\frac{tQ(u)}{(1-t(1+u))^2}+\frac{Q'(u)}{1-t(1+u)}\right) H \\ &= [u^n] \left(Q\cdot k(1+u)^{k-1}+Q'\cdot (1+u)^k\right) H \\ &= k[u^n] (1+u)^{k-1} QH + [u^n] (1+u)^k Q'H \\ &= k\sum\limits_{i=0}^n \binom{k-1}i [x^{n-i}] QH + \sum\limits_{i=0}^n \binom ki [x^{n-i}] Q'H \end{aligned} \]

依然可以卷积。