Educational Codeforces Round 81 F. Good Contest

Problem - F - Codeforces

問題概要

$n$ 問の問題からなるコンテストがある。 $i$ 番目の問題の正解者数は、区間 $\lbrack l_{i}, r_{i}\rbrack$ に含まれる整数の中から等確率で決まる。

問題 $0, 1, ..., n-1$ の正解者数が広義単調減少になる確率を求めよ。これは有理数になるため、 $\bmod 998244353$ で出力せよ。

制約

$2 \le n \le 50$
$0 \le l_{i} \le r_{i} \le 998244351$

解法

問題 $i$ の正解者数を $x_{i}$ と書くことにします。確率よりも場合の数のほうが計算しやすいので、条件を満たすような数列 $(x_{0}, ..., x_{n-1})$ の総数（場合の数）を計算して全事象数で割ることにします。

DPができそうですが、 $l_{i}, r_{r}$ が非常に大きいのが厄介です。座標圧縮ができないか考えましょう。

座標圧縮後に扱いやすくするため、入力の $r_{i}$ に $1$ 加算して半開区間 $\lbrack l_{i}, r_{i})$ として考えます。そしてこれらの座標点を $2n$ 個集めてソートし重複を除いたものが $K$ 個あるとして、これを順に $p_{0},p_{1}, ..., p_{K-1}$ とします。そうすると $x$ の各要素が取りうる値の範囲は区間 $\lbrack p_{0}, p_{1}), ..., \lbrack p_{K-2}, p_{K-1})$ に分割され、これらは重複しないので扱いやすくなります。

区間 $\lbrack p_{j}, p_{j+1})$ を「ゾーン $j$ 」と呼ぶことにします。各問題 $i$ について、区間 $\lbrack l_{i}, r_{i})$ が区間 $\lbrack p_{j}, p_{j+1})$ を含む時、 $x_{i}$ はゾーン $j$ 内に存在し得る（使用可能である）ということになります。

広義単調減少していく数列 $(x_{0}, ..., x_{n-1})$ は、大まかに描くと以下のような遷移をしていきます。各マスが問題とゾーンの組み合わせで、緑マスがその問題の正解者数 $x_{i}$ が属するゾーンです。

f:id:betrue12:20200201015944p:plain

この数列の個数を、例えば以下のようなDPで数え上げられないか考えてみます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ $(x_{0}, ..., x_{i-1})$ までが既に決まっていて、 $x_{i-1}$ がゾーン $j$ に含まれるような場合の数

しかしこれはDPの遷移が上手くいきません。 $dp\lbrack i \rbrack\lbrack j \rbrack$ から遷移するときに、 $x_{i}$ でゾーンを変える場合は問題ないのですが、次も同じゾーン $j$ にいるような場合、ゾーン $j$ の中でも $x_{i-1}$ が具体的にいくつだったのかまで分からないと $x_{i}$ が取れる範囲が分からないからです。

これでは面倒なので、連続する複数の $x_{i}$ が同じゾーンに含まれる場合、それを一気に処理してしまうことを考えます。具体的には以下のように、ゾーンの区切りでのみ状態をまとめるようなDPに変更します。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ $(x_{0}, ..., x_{i-1})$ までが既に決まっていて、 $x_{i-1}$ がゾーン $j$ に含まれていて、 $x_{i-1}$ がゾーン $j$ に含まれる最後の値であるような場合の数

このDPの遷移として、「問題 $i$ からゾーン $j$ が始まって、そこからゾーン $j$ が $l$ 問連続して終わる」という事象を考えましょう。

前提として、問題 $i$ から連続する $l$ 問全てにおいてゾーン $j$ が使用可能である必要があります。最初にこれをチェックします。

遷移元は $k \gt j$ である全ての $k$ から、 $dp\lbrack i \rbrack\lbrack k \rbrack$ を全て持ってきて足し合わせたものです。遷移先は $dp\lbrack i+l \rbrack\lbrack j \rbrack$ になります。このときの係数、つまりゾーン $j$ に含まれる $l$ 個の値の組 $(x_{i}, ..., x_{i+l-1})$ の場合の数を求めましょう。

ゾーン $j$ に属している整数点の個数を $L_{j}$ 個とします。これらの整数を使った要素数 $l$ の広義単調減少数列は、 $L_{j}$ 個の整数から重複を許して順番を区別せずに $l$ 個選び、降順ソートしたものと思うことができます。この重複組合せの選び方と広義単調減少数列は1対1対応するので、その場合の数は $_{L_{j}+l-1}C_{l}$ で求められます。