为了膜拜 EI，口胡翻译一下另一个出题人的做法。
上次看的时候没动脑导致完全无法理解，问 EI 他说一年前写的全忘了（
看了这个暴力推 GF 做法之后感觉这个双射是从 GF 逆推出来的？
我们用 z 元计量序列长度，t 元 tk 的系数表示 k 的出现次数和。
首先为了显得自然，把序列反过来，也就是限制改为 k 的第一次出现之后有 k−1 出现过。
相当有启发意义地，我们发现这个限制的另一面就是所有 k−1 都在所有 k 的前面。
这提示我们容斥。令序列中最大值为 m，枚举 S⊆{1,2,…,m−1} 表示对于 i∈S 强制所有 i 在 i+1 之前出现，然后附有容斥系数 (−1)|S|。
根据经验，这样的钦定就相当于把 [1,m] 的整数划分为若干个 [l,r]，对所有 i∈[l,r−1] 钦定所有 i 出现在 i+1 之前，也就是 [l,r] 内的数要「连续」地出现。
然后段数其实就是 m−|S|，容斥系数也就可以看做每个段尾以外的所有元素都附有一个 −1 的因子。
我们又要同时计数每种元素的出现次数，那么若统计 k，相当于给 [1,k] 的每一个元素都附有一个因子 t 用来刻画元素大小。
而不同段之间我们可以用 EGF 将其位置混合。
那么我们应该统计三个阶段：完整地全部元素都附有 t（完全在需要统计出现次数的 k 之前）的段；包含最后一个 t 的终止段；不包含 t 的段。
对于第一个阶段，一种元素的贡献有至少一个 z 和恰好一个 t，即 tz1−z
然后将此段内的所有元素混合，除去最后一个每一个都附有 −1，且段内非空。那么一段的 OGF 就是 L(z,t)=1−11+tz1−z=tz1−(1−t)z=t∑i≥0(1−t)izi+1
由于不同段之间的位置混合是 EGF，我们考虑其 EGF ˆL(z,t)=t∑i≥0(1−t)izi+1(i+1)!=t1−t∑i≥0(z(1−t))i+1(i+1)!=t1−t(ez(1−t)−1)
对于第二个阶段，一个终止段应当以若干个附有 −t 的元素、一个附有 t 且附有长度的元素、若干个只附有 −1 的元素组成。
也即 U(z,t)=11+tz1−z((zddz)tz1−z)11+z1−z=11+tz1−ztz(1−z)211+z1−z=tz1−(1−t)z=L(z,t)ˆU(z,t)=ˆL(z,t)
对于第三阶段，注意到直接将 t=1 代入先前得出的 ˆL(z,t) 是无意义的。但是注意到 L(z,1)=z 所以 ˆL(z,1)=z。
接下来组合三者，则答案的 EGF 就是 11−ˆL(z,t)ˆU(z,t)11−ˆL(z,1)=t(ez(1−t)−1)(1−z)(1−tez(1−t))
注意到 ([zn]t(ez(1−t)−1)(1−z)(1−tez(1−t)))+1=[zn](t(ez(1−t)−1)(1−z)(1−tez(1−t))+11−z)=(1−t)[zn]1(1−z)(1−tez(1−t))
接下来作换元令 z=u1−t，则 1(1−z)(1−tez(1−t))=(1−t)n[un]1(1−u1−t)(1−teu)
作分式分解，设 1(1−u1−t)(1−teu)=(1−t)1(1−t−u)(1−teu)=(1−t)(A1−t−u+B1−teu)
则 A(1−teu)+B(1−t−u)=1。
令 t=e−u 可得 B=11−e−u−u。
令 t=1−u 可得 A=11−eu+ueu。
所以分解为 e−u(1−eu+ueu)(1−teu)+1(1−eu+ueu)(1−t−u)
先考虑 [un]1(1−eu+ueu)(1−t−u)，容易将其写作 [un+1]P(u)1−t−u，求其 t 的前 n 项只需注意到 P(u)1−t−u=[un+1]P(u)∑i≥0(t+u)i=[un+1]P(u)∑j≥0uj∑i≥j(ij)ti−j≡n+1∑k=0pkn∑i=0(n−k+1+ii)ti(modtn+1)=n∑i=0tin+1∑k=0pk(n−k+1+ii)
可以卷积。
再来考虑 [un]e−u(1−eu+ueu)(1−teu)。
为了容易用拉格朗日反演的形式刻画答案，我们设 F(u)=eu−1，则答案可写为 [un+1]Q(F)1−t(1+F)。
由复合逆 G=F<−1>=ln(1+u) 有 Q(F)1−t(1+F)=1n+1[un](Q(u)1−t(1+u))′(uG(u))n+1=1n+1[un](tQ(u)(1−t(1+u))2+Q′(u)1−t(1+u))(uG)n+1
设 H=(uG)n+1，有 [un](tQ(u)(1−t(1+u))2+Q′(u)1−t(1+u))H=[un](Q∑i≥0(i+1)ti(1+u)i+Q′∑i≥0ti(1+u)i)H
然后 [untk](tQ(u)(1−t(1+u))2+Q′(u)1−t(1+u))H=[un](Q⋅k(1+u)k−1+Q′⋅(1+u)k)H=k[un](1+u)k−1QH+[un](1+u)kQ′H=kn∑i=0(k−1i)[xn−i]QH+n∑i=0(ki)[xn−i]Q′H
依然可以卷积。