We will get the bivariate generating function $$$\widehat 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
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)})}$$$. Here are the details:
Now our goal is to calculate
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. We let $$$z = \frac u{1-t}$$$, then
Hence we have
Noticed that $$$[u^m]\mathrm{e}^{ku} = \frac{k^m}{m!}$$$, this could be calculated straightly through multipoint evaluation with time complexity of $$$\Theta(n\log^2 n)$$$. And $$$[u^m] \frac1{(1-u)^k} = \binom{n+k-1}{n} = \frac{(n+k-1)!}{n!(k-1)!}$$$ so this part could be calculated through a convolution. 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.
UPD1: simplified some deduction.
Auto comment: topic has been updated by Elegia (previous revision, new revision, compare).
Is it competitive coding ?
After seeing this blog, I went your profile to make sure my guess that you are Chinese!
Thanks!
How do you calculate the last part with multipoint evaluation? Elegia
Also, the "tough calculation" part is actually similar to the formula for Eulerian polynomials:
$$$F(x,t) = \displaystyle\sum_{d \ge 0}A_{d}(x)\frac{t^{d}}{d!} = \frac{1-x}{1 - xe^{(1-x)t}},$$$
where $$$A_{d}(x) = \displaystyle\sum_{k=1}^{d}A(d,k)x^{k}$$$ is an Eulerian polynomial. Here, $$$A(d,k)$$$ is the number of permutations of length $$$d$$$ with $$$k-1$$$ descents. We can derive a bijection showing that the answer for $$$k$$$ is $$$n! \cdot \sum_{i=1}^{n}\frac{E(i,k)}{i!}$$$, which is basically the prefix sum of coefficients of $$$F(x,t)$$$, and thus we can simplify "prefix sum" to "coefficient of single term" by multiplying $$$F(x,t)$$$ with $$$\frac{1}{1-t}$$$, which gives the function described in the blog.
For the $$$[u^m] f(u)/(1-t\mathrm{e}^u)$$$ part:
For the $$$[u^m] g(u)/(1-\frac t{1-u})$$$ part, it might cost $$$\Theta(n\log^2 n)$$$ to calculate the coefficient straightly bacause you need to expand the polynomial expressed by the linear combination of $$$\binom{n+x-1}{n}$$$ through divide and conquer.
Speaking of Eulerian Polynomial: Yes, it's surely Eulerian Polynomial. But what I'm going to show is that there is a way to get the GF with no knowledge of Eulerian Polynomial nor bijection to the permutation. It will be updated a few times later. >_<
Can you help me to prove this bijection, please.
I have done it in my tutorial on Generating Functions here.
My implementation: 80415302
In your last expression, $$$(1-t)^{n+2}$$$ should be $$$(1-t)^{n+1}$$$. Or replace the terms after $$$[u^n]$$$ with the following:
corrected, thanks.
stO Elegia! I found that u've been keen on generating function these days XD.
2 years already :)