We will get the bivariate generating function $F(z, t) = \sum_{n\ge 1}\sum_{k=1}^n A_{n,k}\frac{z^nt^k}{n!}$, where $A_{n,k}$ is the sum of occurrences of $k$ in all good sequence of length $n$. Consider the inclusion-exclution principle. For all contribution with $\max k = m$, we have↵
$$↵
\sum_{j=1}^m \sum_{S \subseteq \{1, 2, \cdots m-1\}} (-1)^{|S|} Q(S, z, t, j)↵
$$↵
This means that for all $i \in S$, we force all recurrences of $i$ are before $i + 1$, and the occurrences of $j$ are counted. ↵
↵
After some tough calculation, we will found out that this equates to $\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}$. I will post the details later.↵
↵
Now our goal is to calculate↵
$$↵
[z^n]\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}↵
$$↵
We consider $\left([z^n]\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}\right) + 1 = (1-t)[z^n] \frac 1{(1-z)(1-t\mathrm e^{z(1-t)})}$, which looks simpler.↵
$$↵
\begin{align}[z^n]\frac 1{(1-z)(1-t\mathrm e^{z(1-t)})} & = \sum_{k=0}^\infty t^k [z^n] \frac{\mathrm e^{kz(1-t)}}{1-z}\\&= \sum_{k=0}^\infty t^k \sum_{j=0}^n \frac{(k(1-t))^j}{j!}\\&= \sum_{j=0}^n (1-t)^j\sum_{k=0}^\infty t^k \frac{k^j}{j!} \\&= \sum_{j=0}^n (1-t)^j\sum_{k=0}^\infty t^k [u^j] \mathrm e^{ku}\\&= \sum_{j=0}^n (1-t)^j [u^j] \frac1{1-\mathrm e^u t}\\&= \sum_{j=0}^n (1-t)^{n-j} [u^{n-j}] \frac1{1-\mathrm e^u t}\\&= [u^n] \sum_{j=0}^\infty (1-t)^{n-j} u^j \frac1{1-\mathrm e^u t}\\&= [u^n] (1-t)^n \frac 1{1-\frac u{1-t}}\frac1{1-\mathrm e^u t}\end{align}↵
$$↵
Hence we have↵
$$↵
\begin{aligned}&= [u^n]\frac{(1-t)^{n+2}}{(1-\frac{t}{1-u})(1-t\mathrm e^u)(1-u)}\\&= (1-t)^{n+2} [u^n] \left(\frac{1-\mathrm e^u}{\left(\mathrm e^u u-\mathrm e^u+1\right) \left(1-t \mathrm e^u\right)}+\frac{\frac{u}{1-u}}{\left(\mathrm e^u u-\mathrm e^u+1\right) (1-\frac{t}{1-u})}\right)\end{aligned}↵
$$↵
↵
Noticed that $[u^m]\mathrm{e}^{ku} = \frac{k^m}{m!}, [u^m] \frac1{(1-u)^k} = \binom{n+k-1}{n}$, this could be calculated straightly through multipoint evaluation with time complexity of $\Theta(n\log^2 n)$. It will pass if your implementation doesn't have a big constant.↵
↵
It could also be improved to $\Theta(n\log n)$ through the Lagrange Inversion formula similar to the original solution, I leave this as an exercise.↵
$$↵
\sum_{j=1}^m \sum_{S \subseteq \{1, 2, \cdots m-1\}} (-1)^{|S|} Q(S, z, t, j)↵
$$↵
This means that for all $i \in S$, we force all recurrences of $i$ are before $i + 1$, and the occurrences of $j$ are counted. ↵
↵
After some tough calculation, we will found out that this equates to $\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}$. I will post the details later.↵
↵
Now our goal is to calculate↵
$$↵
[z^n]\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}↵
$$↵
We consider $\left([z^n]\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}\right) + 1 = (1-t)[z^n] \frac 1{(1-z)(1-t\mathrm e^{z(1-t)})}$, which looks simpler.↵
$$↵
\begin{align}[z^n]\frac 1{(1-z)(1-t\mathrm e^{z(1-t)})} & = \sum_{k=0}^\infty t^k [z^n] \frac{\mathrm e^{kz(1-t)}}{1-z}\\&= \sum_{k=0}^\infty t^k \sum_{j=0}^n \frac{(k(1-t))^j}{j!}\\&= \sum_{j=0}^n (1-t)^j\sum_{k=0}^\infty t^k \frac{k^j}{j!} \\&= \sum_{j=0}^n (1-t)^j\sum_{k=0}^\infty t^k [u^j] \mathrm e^{ku}\\&= \sum_{j=0}^n (1-t)^j [u^j] \frac1{1-\mathrm e^u t}\\&= \sum_{j=0}^n (1-t)^{n-j} [u^{n-j}] \frac1{1-\mathrm e^u t}\\&= [u^n] \sum_{j=0}^\infty (1-t)^{n-j} u^j \frac1{1-\mathrm e^u t}\\&= [u^n] (1-t)^n \frac 1{1-\frac u{1-t}}\frac1{1-\mathrm e^u t}\end{align}↵
$$↵
Hence we have↵
$$↵
\begin{aligned}&= [u^n]\frac{(1-t)^{n+2}}{(1-\frac{t}{1-u})(1-t\mathrm e^u)(1-u)}\\&= (1-t)^{n+2} [u^n] \left(\frac{1-\mathrm e^u}{\left(\mathrm e^u u-\mathrm e^u+1\right) \left(1-t \mathrm e^u\right)}+\frac{\frac{u}{1-u}}{\left(\mathrm e^u u-\mathrm e^u+1\right) (1-\frac{t}{1-u})}\right)\end{aligned}↵
$$↵
↵
Noticed that $[u^m]\mathrm{e}^{ku} = \frac{k^m}{m!}, [u^m] \frac1{(1-u)^k} = \binom{n+k-1}{n}$, this could be calculated straightly through multipoint evaluation with time complexity of $\Theta(n\log^2 n)$. It will pass if your implementation doesn't have a big constant.↵
↵
It could also be improved to $\Theta(n\log n)$ through the Lagrange Inversion formula similar to the original solution, I leave this as an exercise.↵
