## Ex - Random Painting 解説 by en_translator

### 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}$$ 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.

Spoiler

Consider a polynomial $g(x) = \sum_{i=0}^{M} f(i)x^i$. Then, the DP for finding $g(x)$ for some $x$ can be done by means of segment product and segment sum form, which can be computed on lazy segment trees. Therefore, it can be solved in an $O(M \log N)$ time.

By finding $g(x)$ for $(M+2)$ different $x$'s, we can recover $f(0),f(1),\ldots,f(M)$ by Lagrange's interpolation in a total of $O(M^2)$ time.