問題一覧 > 通常問題

No.1214 Market

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 6
作問者 : penguinmanpenguinman / テスター : kaagekaage
0 ProblemId : 5034 / 出題時の順位表
問題文最終更新日: 2020-08-30 14:21:17

問題文

Penguinman は市場を運営しています。
この市場では、この時点で以下の $4$ つのことが決まっています。
・$N$ 人の客が来ること。
・$M$ 個の品物を売ること。それぞれの品物には値段と価値が定まっており、$i$ 個目の品物の値段は $A_i$ 円,価値は $B_i$ である。ただし、 $i≠j$ ならば $B_i≠B_j$ であることが保証される。
・全ての客は $0$ 円以上 $K$ 円以下のうち好きな金額(整数)を等しい確率で持ってくること。
・客は持ってきたお金で買えるもののうち最も価値の高いものを $1$ つだけ買うこと。買われた品物はその時点で市場からなくなる(14:20 追記)。買えるものがない時は買い物を諦めて帰ることとし、またこの問題の制約のもと買う品物は一意に定まる。
Penguinman は、それぞれの客が持ってくる金額が分かってから、客が買う品物の価値の総和が最大になるように、 彼の決めた自由な順番で $1$ 人ずつ (14:16 修正) 市場で買い物をさせます。
Penguinman の部下であるあなたの仕事は、客が買う品物の価値の総和の期待値を求めることです。
この期待値は $2$ つの正の整数 $P,Q$ を用いて $P/Q$ で表すことができることが保証されるので、 $R×Q≡P(\bmod 10^9+7)$ となるような $0$ 以上 $10^9+6$ 以下の整数 $R$ を求め、出力してください。

入力

$N\ M\ K$
$A_1\ B_1$
$A_2\ B_2$
:
$A_M\ B_M$

・$1≤N,M≤40$
・$1≤K≤10^9$
・$1≤A_i≤K$
・$1≤B_i≤10^9$
・$i≠j$ ならば $B_i≠B_j$
・入力は全て整数

出力

最後に改行してください。

サンプル

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

$2$ 人ともが $1$ 円も持ってこなかった場合に限り買われる品物の価値の総和は $0$ になり、その他の場合は総和は $1$ になります。
よって期待値は $8/3^2=8/9$ となるため、出力すべき値は $R×9≡8(\bmod 10^9+7)$ となる整数 $R$ であり、 $888888896$ が答えとなります。

サンプル2
入力
10 3 100
2 4
5 100
1 101
出力
974312872

サンプル3
入力
40 6 1000000
400 100
20 1
1030 11
593 103
194029 103948
20 9183
出力
621015348

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