はじめに

問題文中では、箱の中から等確率で一つのボール \(x\) を引き、それに対応する区間 \([L_x,R_x]\) を黒く塗り潰していましたが、この解説では簡略化のため、箱の中から直接区間 \(x\) を引き、\([L_x,R_x]\) を黒く塗り潰すこととします。

本題

この問題の答えは、\(M\) 個の区間 \([L_1,R_1],\ [L_2,R_2],\ \ldots,\ [L_M,R_M]\) の \(2^M\) 通りある部分集合 \(S\) のうち、\(S\) に含まれる区間の和集合が \([1,N]\) にならないものすべてについて「\(N\) 個のマスがすべて黒く塗られるまでの過程において一度以上、『箱から取り出された区間の集合が \(S\) と一致する』という事象が起きる確率」と「区間の集合が \(S\) と一致したとき、\(S\) に含まれない区間が箱の中から引かれるまでにかかる操作回数の期待値」の積を求め、それを足し合わせたものに等しくなります（☆）。

\(f(i)\) を、\(M\) 個の区間 \([L_1,R_1],\ [L_2,R_2],\ \ldots,\ [L_M,R_M]\) の \(2^M\) 通りある部分集合 \(S\) のうち、\(S\) に含まれる区間の和集合が \([1,N]\) になり、かつ \(S\) に含まれる区間の個数が \(i\) であるようなものの個数と定義します。

すると☆より、求める期待値は

• \(\sum_{i=0}^{N} \frac{\binom{M}{i}-f(i)}{\binom{M}{i}} \times \frac{M}{M-i}\)

に等しくなります。

\(i=0,1,\ldots,M\) について \(f(i)\) を求めることを考えましょう。

手始めに、\(M\) 個の区間を \(L_i\) の昇順 → \(R_i\) の昇順にソートします。その上で、以下の動的計画法を考えます。

• \(\text{dp}[i][j][k]:=(\)区間 \(1\)、区間 \(2\)、\(\cdots\)、区間 \(i\) の部分集合 \(S\) のうち、\(S\) に含まれる区間の和集合が \([1,j]\) と一致し、かつ \(S\) に含まれる区間の個数が \(k\) であるようなものの個数\()\)

はじめ \(\text{dp}[0][0][0]\) を \(1\) で、それ以外の要素を \(0\) で初期化し、その上で、遷移は \(i\) の昇順に以下を行うとよいです。

• \(j=N,N-1,\ldots,1,0\)（注1）、\(k=0,1,\ldots,i\) について、
  • \(j \lt L_i-1\) なら
    • \(\text{dp}[i][j][k]\) に \(\text{dp}[i-1][j][k]\) を代入する
  • \(L_i-1 \leq j \leq R_i\) なら
    • \(\text{dp}[i][j][k]\) に \(\text{dp}[i-1][j][k]\) を代入する
    • \(\text{dp}[i][R_i][k]\) に \(\text{dp}[i-1][j][k-1]\) を加算する（ただし \(0 \lt k\)）
  • \(R_i \lt j\) なら
    • \(\text{dp}[i][j][k]\) に \(\text{dp}[i-1][j][k]\) を代入する（\(k=0\) の場合）
    • \(\text{dp}[i][j][k]\) に \(\text{dp}[i-1][j][k-1]+\text{dp}[i-1][j][k]\) を代入する（\(0 \lt k\) の場合）

求めたい値 \(f(k)\) は、\(\text{dp}[M][N][k]\) と等しくなります。計算量は \(O(NM^2)\) です。

注1：\(j\) が降順なのは、\(j=R_i\) における代入処理と \(L_i-1 \leq j \lt R_i\) における加算処理が衝突しないようにするためです。

実装例 (C++)

実装例 (PyPy3)

おまけ

三乗解との区別が厳しかったため \(O(NM^2)\) を許容する制約となっていますが、この問題は \(O(M^2 \log N)\) で解くことも可能です。

方針としては以下のようなものがあります。

ネタバレ

多項式 $g(x) = \sum_{i=0}^{M} f(i)x^i$ を考える。すると、ある $x$ についての $g(x)$ を求める dp は遷移が区間乗算・区間和の形になり、これは遅延セグ木に乗る。そのため $O(M \log N)$ で解くことができる。

$M+2$ 個の相異なる $x$ について $g(x)$ を求めると、ラグランジュ補間により $O(M^2)$ で $f(0),f(1),\ldots,f(M)$ を復元することができる。