Slime and Sequences
https://codeforces.com/contest/1349/problem/F2
Two days' hard work.
Firstly, consider the total number of this kind of sequences.
Interpret the statement, the number used is a interval \([1,m]\) and , \(i\) cannot appear totally before \(i-1\)
so the illegal relation form a partition of \([1,m]\) , and one component means that \([i,j]\) is placed in reverse order. ( .i.e j....j.....j....j-1....j-1....j-1.....j-2......j-2......i...i..)
Using PIE, one can obtain the following gf.
\[\frac{1}{1-\sum_{k\ge1}x^k\sum_{j\ge k}\frac{y^j}{j!}\binom{j-1}{k-1}(-1)^{k-1}}=\frac{1-x}{1-xe^{y(1-x)}}
\]
Here, \([x^m]\) means we use \(m\) numbers, \([y^n]\) means the length of sequence is \(n\).
(In fact this is Eulerian number, but this is not important)
Because we are concerned about how many times a certain number appear, we calculate answer for number v.
\[\sum_m\sum_i i\sum_{l\le v \ r\ge v}\sum_j\binom{j-i-1}{r-l-1}\frac{y^j}{j!}(-1)^{r-l}(\frac{1-x}{1-xe^{y(1-x)}}[x^{l-1}])(\frac{1-x}{1-xe^{y(1-x)}}[x^{m-r}])
\]
here \(l=r\) need special consideration, we can assume\(\binom{-1}{-1}=1\)
note that
\[\sum_m\frac{1-x}{1-xe^{y(1-x)}}[x^{m-r}][y^n]=\frac{1}{1-xe^{y(1-x)}}[x^n][y^n]=\frac{1}{n!}\sum_k\binom{n}{k}(-1)^{n-k}k^n=1
\]
continue
\[=\sum_i i\sum_{l\le v \ r\ge v}\sum_j\binom{j-i-1}{r-l-1}\frac{y^j}{j!}(-1)^{r-l}(\frac{1-x}{1-xe^{y(1-x)}}[x^{l-1}])(\frac{1}{1-y})
\]
for convenience. Introduce a new variable and extract \([z^v]\)
\[\sum_i i\sum_{l\le r}\frac{z^l-z^{r+1}}{1-z}\sum_j\binom{j-i-1}{r-l-1}\frac{y^j}{j!}(-1)^{r-l}(\frac{1-x}{1-xe^{y(1-x)}}[x^{l-1}])(\frac{1}{1-y})
\]
spiltting it into three parts.
part 1
\[\sum_i i\sum_{l<r}\frac{z^l}{1-z}\sum_j\binom{j-i-1}{r-l-1}\frac{y^j}{j!}(-1)^{r-l}(\frac{1-x}{1-xe^{y(1-x)}}[x^{l-1}])(\frac{1}{1-y})
\]
\[=-\sum_i i\sum_l\frac{z^l}{1-z}\frac{y^{i+1}}{(i+1)!}(\frac{1-x}{1-xe^{y(1-x)}}[x^{l-1}])(\frac{1}{1-y})
\]
\[=-\frac{z}{1-z}\sum_i i\frac{y^{i+1}}{(i+1)!}(\frac{1-z}{1-ze^{y(1-z)}})(\frac{1}{1-y})
\]
\[=\frac{z(-ye^y+e^y-1)}{(1-y)(1-ze^{y(1-z)})}
\]
part 2
\[\sum_i i\sum_{l< r}\frac{-z^r}{1-z}\sum_j\binom{j-i-1}{r-l-1}\frac{y^j}{j!}(-1)^{r-l}(\frac{1-x}{1-xe^{y(1-x)}}[x^{l-1}])(\frac{1}{1-y})
\]
\[=\sum_i i\sum_{l}\frac{z^{l+2}}{1-z}\sum_j(1-z)^{j-i-1}\frac{y^j}{j!}(\frac{1-x}{1-xe^{y(1-x)}}[x^{l-1}])(\frac{1}{1-y})
\]
\[=\sum_i i\frac{z^3}{1-z}\sum_j(1-z)^{j-i-1}\frac{y^j}{j!}(\frac{1-z}{1-ze^{y(1-z)}})(\frac{1}{1-y})
\]
\[=\frac{z}{1-z}\sum_j((1-z)^{j}+jz-1)\frac{y^j}{j!}(\frac{1-z}{1-ze^{y(1-z)}})(\frac{1}{1-y})
\]
\[=\frac{z(e^{y(1-z)}-e^y+yze^y)}{(1-y)(1-ze^{y(1-z)})}
\]
part 3
\[\sum_i i\sum_{l= r}\frac{z^l-z^{r+1}}{1-z}\sum_j\frac{y^j}{j!}(-1)^{r-l}(\frac{1-x}{1-xe^{y(1-x)}}[x^{l-1}])(\frac{1}{1-y})
\]
\[=\frac{ye^y(1-z)z}{(1-y)(1-ze^{y(1-z)})}
\]
combine three parts we only need the polynomial of \(z\)
\[\frac{ze^{y(1-z)}-z}{(1-y)(1-ze^{y(1-z)})}[y^n]=-\frac{1}{1-y}+\frac{1-z}{(1-y)(1-ze^{y(1-z)})}[y^n]
\]
for the second term, use change of variable
\[\frac{(1-z)^{n+1}}{(1-\frac{y}{1-z})(1-ze^{y})}[y^n]=(1-z)^{n+2}\frac{1}{-e^y(1-y)+1}(\frac{-e^y}{1-ze^y}+\frac{1}{1-y-z})[y^n]
\]
the second part can be calculated with a convolution because we can get for every \(k\) can and fixed \(n\)
\(F(x)(1+x)^k[x^n]\) and \(F(x)(1-x)^{-k}[x^n]\)
for the first part, Do Lagrange Inversion. \(t=e^y-1\) have compositional inverse.
and then we only need to deal with the denominator with the form \(1-z(t+1)\) and extract some \([t^n]\)
this is the same as the above convolution.