支持一下 Qiuly /tyt
为了膜拜 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$，即
$$
\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} ( {\rm 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{ {\rm d} }{ {\rm 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( {\rm e} ^{z(1-t)}-1)}{(1-z)(1-t {\rm e} ^{z(1-t)})}
$$
注意到
$$
\begin{aligned}
& \quad \; \left([z^n] \frac{t( {\rm e} ^{z(1-t)}-1)}{(1-z)(1-t {\rm e} ^{z(1-t)})}\right) + 1 \\
&= [z^n] \left(\frac{t( {\rm e} ^{z(1-t)}-1)}{(1-z)(1-t {\rm e} ^{z(1-t)})} + \frac 1{1-z}\right) \\
&= (1-t) [z^n] \frac1{(1-z)(1-t {\rm e} ^{z(1-t)})}
\end{aligned}
$$
接下来作换元令 $z = \frac u{1-t}$，则
$$
\begin{aligned}
[z^n] \frac1{(1-z)(1-t {\rm e} ^{z(1-t)})} = (1-t)^n [u^n] \frac1{\left(1-\frac u{1-t}\right)(1-t {\rm e} ^u)}
\end{aligned}
$$
作分式分解，设
$$
\begin{aligned}
\frac1{\left(1-\frac u{1-t}\right)(1-t {\rm e} ^u)}
&= (1-t)\frac1{(1-t-u)(1-t {\rm e} ^u)} \\
&= (1-t)\left(\frac A{1-t-u} + \frac B{1-t {\rm e} ^u}\right)
\end{aligned}
$$
则 $A(1-t {\rm e} ^u) + B(1-t-u) = 1$。
令 $t = {\rm e} ^{-u}$ 可得 $B = \frac1{1- {\rm e} ^{-u}-u}$。
令 $t = 1-u$ 可得 $A = \frac1{1- {\rm e} ^u+u {\rm e} ^u}$。
所以分解为
$$
\frac{ {\rm e} ^{-u} }{(1- {\rm e} ^u+u {\rm e} ^u)(1-t {\rm e} ^u)} + \frac1{(1- {\rm e} ^u+u {\rm e} ^u)(1-t-u)}
$$
先考虑 $[u^n]\frac1{(1- {\rm e} ^u+u {\rm 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{ {\rm e} ^{-u} }{(1- {\rm e} ^u+u {\rm e} ^u)(1-t {\rm e} ^u)}$。
为了容易用拉格朗日反演的形式刻画答案，我们设 $F(u) = {\rm 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}
$$
依然可以卷积。
0 条评论