H - Mission
問題文
つくば市には $N$ 個の町があり、町の間には $M$ 本のバスが走っている。$i$ 番目のバスは時刻 $L_i$ に町 $S_i$ を出発し、時刻 $R_i$ に町 $T_i$ に到着する。乗り換えの時間は考えない。
時刻 $0$ から時刻 $D$ までのどこかのタイミングで、町のうち $1$ つがランダムに選ばれ Yu くんに通知される。Yu くんの目標は、通知から $K$ 単位時間以内に、選ばれた町に移動することである。ただし、通知のタイミングは $0$ 以上 $D$ 以下の任意の実数から、選ばれる町は $1$ 以上 $N$ 以下の任意の整数からそれぞれ一様ランダムに決められる。
この目標を達成するために、Yu くんは町の間をバスを使って自由に移動することができる。また、時刻 $0$ 時点でいる町を任意に決めることができる。
Yu くんが目標を達成できる確率を最大化するように適切に移動したとき、目標を達成できる確率を $\text{mod }(10^9+7)$ で求めよ。
「確率を $\text{mod }(10^9+7)$ で求める」とは
求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P,Q$ を用いて $P/Q$ と表したとき、 $R\times Q\equiv P\ \pmod{10^9+7}$ かつ $0\leq R\lt 10^9+7$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。制約
- $1\leq N \leq 1000$
- $1\leq M\leq 1000$
- $1 \leq D,K \leq 10^9$
- $0\leq L_i < R_i \leq D+K \leq 10^9\ \ (1\leq i \leq M)$
- $1\leq S_i, T_i \leq N\ \ (1\leq i \leq M)$
- $S_i \neq T_i\ \ (1\leq i \leq M)$
- 入力される値はすべて整数
入力
入力は以下の形式で与えられる。
$N\quad M\quad D\quad K$
$L_1\quad R_1\quad S_1\quad T_1$
$L_2\quad R_2\quad S_2\quad T_2$
$\vdots$
$L_M\quad R_M\quad S_M\quad T_M$
出力
答えを出力せよ。
2 2 4 2
1 2 1 2
3 5 2 1
625000005
Yu くんは、以下の戦略にしたがって行動することで、目標の達成確率を $5/8$ にすることができます。
- 時刻 $0$ の時点で町 $1$ からスタートする。
- 時刻 $1$ までに町 $1$ が通知された場合はそのまま目標を達成する。そうでない場合は $1$ 番目のバスを使って町 $2$ に移動する。
目標の達成確率を $5/8$ より大きくすることはできないため、これが答えとなります。$5/8 \equiv 625000005 \pmod {10^9+7}$ より、$625000005$ を出力します。
4 3 6 3
0 2 1 3
2 4 3 2
5 7 2 4
333333336
適切に行動すると、$1/3$ の確率で目標を達成できます。
10 20 60 30
0 8 1 2
3 18 2 3
10 24 3 4
15 35 4 5
28 40 5 6
32 50 6 7
45 60 7 8
50 75 8 9
55 85 9 10
12 30 2 5
5 22 4 1
18 33 6 3
22 48 7 4
30 52 8 6
36 58 9 7
40 70 10 2
6 27 3 6
26 44 5 8
48 78 1 9
20 45 10 1
835000006
適切に行動すると、$31/200$ の確率で目標を達成できます。