First of all

In the problem statement, a ball \(x\) is picked up from the box and the corresponding segment \([L_x,R_x]\) is painted black, but in this editorial, for simplicity, assume that segment \(x\) is directly picked up from the box and \([L_x,R_x]\) is painted black.

Main article

The answer for this problem is equal to the sum, for all subset \(S\) of the \(M\) segments \([L_1,R_1],\ [L_2,R_2],\ \ldots,\ [L_M,R_M]\) (thus \(S\) is one of \(2^M\) possible subsets) such that the union set of the segments in \(S\) is not \([1,N]\), of the product of “the probability of the event where, during the process until all the \(N\) squares are painted black, the set of segments picked up from the box never becomes \(S\)” and “the expected value of the number of operations until a segment not contained in \(S\) is picked up from the box when the set of segments coincides with \(S\)”. (☆)

Let \(f(i)\) be the number of subsets \(S\) of the \(M\) segments \([L_1,R_1],\ [L_2,R_2],\ \ldots,\ [L_M,R_M]\) (thus \(S\) is one of \(2^M\) possible subsets) such that the union set of the segments in \(S\) is \([1,N]\) and that the number of segments in \(S\) is \(i\).

Then, by ☆, the desired expected value is equal to

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

Now, let us consider how to find \(f(i)\) for \(i=0,1,\ldots,M\).

First of all, sort the \(M\) segments in the increasing order of \(L_i\), then in the increasing order of \(R_i\). Then, consider the following Dynamic Programming (DP):

• \(\text{dp}[i][j][k]:=(\)the number of subsets \(S\) of Segment \(1\), Segment \(2\), \(\ldots\), and Segment \(i\), such that the union set the segments in \(S\) coincides to \([1,j]\) and the number of segments in \(S\) is \(k\)).

First, initialize \(\text{dp}[0][0][0]\) with \(1\) and the other elements with \(0\); then, do the transition in the increasing order of \(i\) as follows.

• For \(j=N,N-1,\ldots,1,0\) (note 1) and \(k=0,1,\ldots,i\),
  • if \(j \lt L_i-1\),
  • let \(\text{dp}[i][j][k]\) be \(\text{dp}[i-1][j][k]\);
  • if \(L_i-1 \leq j \leq R_i\),
  • let \(\text{dp}[i][j][k]\) be \(\text{dp}[i-1][j][k]\),
  • add \(\text{dp}[i-1][j][k-1]\) to \(\text{dp}[i][R_i][k]\) (if \(0 \lt k\));
  • if \(R_i \lt j\),
  • let \(\text{dp}[i][j][k]\) be \(\text{dp}[i-1][j][k]\) (if \(k=0\));
  • let \(\text{dp}[i][j][k]\) be \(\text{dp}[i-1][j][k-1]+\text{dp}[i-1][j][k]\) (if \(0 \lt k\)).

The desired value \(f(k)\) is equal to \(\text{dp}[M][N][k]\). The time complexity is \(O(NM^2)\).

Note 1: \(j\) is iterated in the decreasing order so that the assignment for \(j=R_i\) and the addition for \(L_i-1 \leq j \lt R_i\) do not collide.

Sample code (C++)

Sample code (PyPy3)

Bonus

Since it was difficult to distinguish from the cubic solution, the Constraints are set so that \(O(NM^2)\) is also tolerated, but this problem can also be solved in a total of \(O(M^2 \log N)\) time.

The following method is possible.