時間はすべて秒に変換しておく.

\(\sum S_i \leq L\) ならば1周以上するので \(N\) が答えとなる. 以下は \(\sum S_i \gt L\) の場合を考える.

最後に流れる曲を \(j\) とすると, \(j\) 以外の曲を使って \(L-S_j\) 以上 \(L\) 未満の長さが作れればいいことになる. \(i\) 番目の曲まで見たときに \(c\) 曲使って \(t\) 秒使うときの順序を考えない組み合わせの数を \(C_j(i, c, t)\) とする. これはDPを使って,

\[C_j(i, c, t) = C_j(i-1, c, t) + C_j(i-1, c-1, t-S_i)\]

とすれば求められる. なお, \(\combi{50}{25} \lt 10^{15}\) なので long の範囲で収まる.

\(C_j(N-1, c, t)\) が求まったならば, \([L-S_j, L)\) 間の \(t\) および \(c\) に対して,

\[(c+1) \times \frac{C_j(N-1, c, t) \times c! \times (N-1-c)!}{N!}\]

が最後に流れる曲が \(j\) になるときの期待値である. これをすべての \(j\) について計算して足し合わせればいい.

しかし, 計算量が \(O(N^3L)\) となるのでギリギリ足りるかどうかとなる.

そこで, 戻すDPを使う.

すべての曲を使って同じように順序を考えない組み合わせの数を \(D(i, c, t)\) とすると, 同じように

\[D(i, c, t) = D(i-1, c, t) + D(i-1, c-1, t-S_i)\]

となり, これを変形して,

\[D(N-1, c, t) = D(N, c, t) - D(N-1, c-1, t-S_N)\]

となる. 曲の選び順には任意なので, 最後に曲 \(j\) を選んだと仮定すると, \(D(N-1, c, t) = C_j(N-1, c, t)\) となるので, 1回のDPは \(O(NL)\) で行えるようになり, 全体の計算量は \(O(N^2L)\) となる.