(The input variable \(X\) is confusing with the formal power series variable \(x\), so we represent the input \(X\) as \(M\).)

The approach is basically the same as the official editorial, but using formal power series makes it clearer and improves the time complexity.

Let \(f=\displaystyle\frac{1}{N}\sum_{i=1}^{N}\ x^{T_i}\) be the formal power series that describe one playback. The formal power series whose coefficient of \(x^t\) show the probability that songs switch at time \(t\) is described as \(\displaystyle\sum_{k=0}^{\infty}f^k\).

Taking into account that the first track lasts for \(T_1\) seconds, the desired probability can be calculated as

\[ [x^M] \displaystyle\frac{1}{N}(1+x+\cdots+x^{T_1-1})\sum_{k=0}^{\infty}f^k =[x^M] \displaystyle\frac{1-x^{T_1}}{N(1-x)}\frac{1}{1-f} \]

This can be done by multiplication and division of formal power series up to degree \(M\). Including the input, the time complexity is \(O(N+M\log M)\).

AC Code (PyPy 3)