問題概要
問の問題からなるコンテストがある。
番目の問題の正解者数は、区間
に含まれる整数の中から等確率で決まる。
問題 の正解者数が広義単調減少になる確率を求めよ。これは有理数になるため、
で出力せよ。
制約
解法
問題 の正解者数を
と書くことにします。確率よりも場合の数のほうが計算しやすいので、条件を満たすような数列
の総数(場合の数)を計算して全事象数で割ることにします。
DPができそうですが、 が非常に大きいのが厄介です。座標圧縮ができないか考えましょう。
座標圧縮後に扱いやすくするため、入力の に
加算して半開区間
として考えます。そしてこれらの座標点を
個集めてソートし重複を除いたものが
個あるとして、これを順に
とします。そうすると
の各要素が取りうる値の範囲は区間
に分割され、これらは重複しないので扱いやすくなります。
区間 を「ゾーン
」と呼ぶことにします。各問題
について、区間
が区間
を含む時、
はゾーン
内に存在し得る(使用可能である)ということになります。
広義単調減少していく数列 は、大まかに描くと以下のような遷移をしていきます。各マスが問題とゾーンの組み合わせで、緑マスがその問題の正解者数
が属するゾーンです。
この数列の個数を、例えば以下のようなDPで数え上げられないか考えてみます。
までが既に決まっていて、
がゾーン
に含まれるような場合の数
しかしこれはDPの遷移が上手くいきません。 から遷移するときに、
でゾーンを変える場合は問題ないのですが、次も同じゾーン
にいるような場合、ゾーン
の中でも
が具体的にいくつだったのかまで分からないと
が取れる範囲が分からないからです。
これでは面倒なので、連続する複数の が同じゾーンに含まれる場合、それを一気に処理してしまうことを考えます。具体的には以下のように、ゾーンの区切りでのみ状態をまとめるようなDPに変更します。
までが既に決まっていて、
がゾーン
に含まれていて、
がゾーン
に含まれる最後の値であるような場合の数
このDPの遷移として、「問題 からゾーン
が始まって、そこからゾーン
が
問連続して終わる」という事象を考えましょう。
前提として、問題 から連続する
問全てにおいてゾーン
が使用可能である必要があります。最初にこれをチェックします。
遷移元は である全ての
から、
を全て持ってきて足し合わせたものです。遷移先は
になります。このときの係数、つまりゾーン
に含まれる
個の値の組
の場合の数を求めましょう。
ゾーン に属している整数点の個数を
個とします。これらの整数を使った要素数
の広義単調減少数列は、
個の整数から重複を許して順番を区別せずに
個選び、降順ソートしたものと思うことができます。この重複組合せの選び方と広義単調減少数列は1対1対応するので、その場合の数は
で求められます。
ここで二項係数を求める際に は非常に大きくなり得ますが、
が十分小さいので以下の式を利用して求めれば良いです。
これでDPの遷移が計算できます。
以下のコードは の3重ループ内で毎回二項係数を求めているので
になりますが、定数倍も小さいので十分通ります。二項係数を前計算したり
を伸ばしていきながら逐次的に計算すると
になりますね。