問題一覧 > 通常問題

No.907 Continuous Kadomatu

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : pekempeypekempey / テスター : 37zigen37zigen
6 ProblemId : 2900 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-11 18:16:10

問題文

長さ $N$ の"実数"の数列 $a_1,\ldots,a_N$ を以下の方法で作ったとき、作った数列が門松列になる確率を求めてください。

  • $A_i$ 以上 $B_i$ 以下の"実数"を一様ランダムに選び $a_i$ とする。

数列 $a_1,\ldots,a_N$ が門松列であるとは $a_1 \le a_2 \ge a_3 \le a_4 \ge a_5 \le \cdots $ であることを言います。つまりすべての $1 \le i \le N-1$ に対して以下が成り立つことを言います。

  • $i$ が奇数ならば $a_i \le a_{i+1}$ である。
  • $i$ が偶数ならば $a_i \ge a_{i+1}$ である。

作る数列は整数列ではなく"実数列"であることに気をつけてください。

入力

$N$
$A_1\ B_1$
$\vdots$
$A_N\ B_N$

$3 \le N \le 200$
$1 \le A_i < B_i \le 10^9$
入力はすべて整数である。

出力

答えは既約分数 $p/q$ の形で表せるので $p\,q^{-1} \bmod{10^9+7}$ を出力してください。つまり $xq \equiv p \pmod{10^9+7}$ を満たす最小の非負整数 $x$ を出力してください。この問題ではこの値はかならず存在します。

サンプル

サンプル1
入力
3
1 3
1 3
1 3
出力
333333336

答えは $1/3$ です。ランダムに三つの実数を生成したとき二番目の値が最大になる確率と言い換えられますが対称性から $1/3$ になります。作る数列は整数列ではなく"実数列"であることに気をつけてください。

サンプル2
入力
3
1 2
2 3
1 2
出力
1

答えは $1/1$ です。

サンプル3
入力
3
2 3
1 2
2 3
出力
0

答えは $0/1$ です。門松列としてありえるのは $2,2,2$ だけですが現れる確率は $0$ です。

サンプル4
入力
5
1 4
2 3
1 3
2 4
1 4
出力
715740746

答えは $269/1080$ です。

サンプル5
入力
9
766526787 974319581
941243410 942612052
427056305 964028266
313356130 664522966
480128631 531723103
1626524 615851774
293907611 496577233
1955784 467846274
83687962 802560435
出力
175278186

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。