为了膜拜 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} \]
依然可以卷积。