（形式的べき級数の変数 \(x\) と入力の \(X\) が紛らわしいので、入力の \(X\) を \(M\) で表します。）

考え方は 公式解説 と同様ですが、形式的べき級数を用いて表すと見通しが良くなり、計算量も改善できます。

時刻 \(t\) 秒に曲が切り替わる確率 \(p_t\) を \(x^t\) の係数とするべき級数は、 \(1\) 回の再生による変動 \(f=\displaystyle\frac{1}{N}\sum_{i=1}^{N}\ x^{T_i}\) を用いて、 \(\displaystyle\sum_{k=0}^{\infty}f^k\) と表せます。

\(1\) 番目の曲が \(T_1\) 秒継続することも考慮すると、求める確率は

\[ [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} \]

と表せます。これは \(M\) 次までの形式的べき級数の乗除ができればよく、入力と合わせて \(O(N+M\log M)\) で計算できます。

AC コード例 （PyPy 3）