Another solution of CF#641 F2

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

$$$ \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)})}$$$. Here are the details:

Details

This part will be kind of hard to understand because I used some of my own symbols in solving combinatorial problems. I tried to remove some of them unfortunately it's still so abstract.

We consider changing the order of calculation. Because those $$$(-1)$$$ connected several consecutive "$$$k$$$"s, we enumerate the consecutive "segment" of $$$k$$$. Then we should count the occurrences of $$$k$$$ and multiply it with $$$t^k$$$. So this could be represented with a sum of this kind of structure:

$$$ \overbrace{\left.\bigcirc {\color{blue}(\cdot t)} \frac{\tiny \color{red} -1}{}\bigcirc {\color{blue}(\cdot t)} \frac{\tiny \color{red} -1}{} \cdots \frac{\tiny \color{red} -1}{} \bigcirc {\color{blue}(\cdot t)} \middle\vert \cdots \middle\vert \bigcirc {\color{blue}(\cdot t)} \frac{\tiny \color{red} -1}{}\cdots \frac{\tiny \color{red} -1}{} {\color{green}\bigcirc} {\color{blue}(\cdot t)}{\color{green}(\cdot \mathrm{Len})} \right.}^{\mathrm{with} {\color{blue}(\cdot t)}} \left. \frac{\tiny \color{red} -1}{} \cdots \frac{\tiny \color{red} -1}{} \bigcirc \middle\vert \cdots \middle\vert \bigcirc \frac{\tiny \color{red} -1}{}\bigcirc \frac{\tiny \color{red} -1}{} \cdots \frac{\tiny \color{red} -1}{} \bigcirc \right. $$$

Here $$$\bigcirc$$$ means all elements with number $$$k$$$, and $$$-$$$ means the restriction between two numbers, $$$|$$$ means no restriction.

For a consecutive segment of "$$$k$$$"s with restriction, it's easy to be represented by OGF. The last combination between them could be expressed by EGF.

The OGF have 3 parts. The first part contains $$$t$$$s. The second part contains the ending of $$$t$$$ and counts the occurrence. The third part doesn't contain $$$t$$$.

For the first part:

$$$ \begin{aligned} L(z,t) &=\frac{-1}{1+\frac z{1-z}t} + 1 \\ &= \frac{t z}{1-(1-t) z}\\ &= \sum_{k\ge 0} z^{k+1} t(1-z)^k\\ \widehat L(z,t) &= \frac t{1-t}\sum_{k\ge 0} \frac{z^{k+1}}{(k+1)!} (1-t)^{k+1}\\ &= \frac t{1-t} (\mathrm e^ {z(1-t)} - 1) \end{aligned} $$$

For the second part:

$$$ \begin{aligned} U(z,t) &= \frac1{1+\frac z{1-z}t} \frac {zt}{(1-z)^2} \frac1{1+\frac z{1-z}}\\ &= \frac{tz}{1-(1-t)z} = L(z,t)\\ \widehat U(z,t)&= \widehat L(z,t) \end{aligned} $$$

For the third part it's easy to know that $$$L(z, 1) = z = \widehat L(z, 1)$$$. So the EGF of our destination is

$$$ \frac1{1-\widehat L(z,t)} \widehat U(z, t) \frac 1{1 - \widehat L(z, 1)} $$$

After the simplication we have $$$\frac{t(\mathrm e^{z(1-t)}-1)}{(1-z) (1-t \mathrm e^{z(1-t)})}$$$.

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. We let $$$z = \frac u{1-t}$$$, then

$$$ [z^n]\frac 1{(1-z)(1-t\mathrm e^{z(1-t)})} = (1-t)^n[u^n] \frac1{(1-\frac u{1-t})(1-t\mathrm{e}^u)} $$$

Hence we have

$$$ \begin{aligned} (1-t)[z^n] \frac 1{(1-z)(1-t\mathrm e^{z(1-t)})} &= [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{-\mathrm e^u}{\left(\mathrm e^u u-\mathrm e^u+1\right) \left(1-t \mathrm e^u\right)}+\frac{\frac{1}{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!}$$$, 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.

Rev.	By	When	Δ	Comment
en10	Elegia	2020-05-19 19:30:35	69
en9	Elegia	2020-05-19 19:29:25	1057	(published)
en8	Elegia	2020-05-19 19:12:46	1930	(saved to drafts)
en7	Elegia	2020-05-17 04:44:25	176
en6	Elegia	2020-05-13 16:57:10	585
en5	Elegia	2020-05-12 19:18:18	0	(published)
en4	Elegia	2020-05-12 19:12:23	2
en3	Elegia	2020-05-12 19:05:08	169
en2	Elegia	2020-05-12 19:02:40	45
en1	Elegia	2020-05-12 18:56:10	2116	Initial revision (saved to drafts)

History