K - ルーレット

Contest Duration: 2019-04-30(Tue) 04:00 - 2019-04-30(Tue) 09:00 (local time) (300 minutes) Back to Home

K - ルーレット Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $600$ 点

この問題の解説はこちら。

問題文

いろはちゃんは、 $N$ 個のルーレット用の円盤と十分な個数のルーレット用の球を持っています。各円盤には $1$ から $N$ までの整数番号が割り振られています。

円盤の周囲には整数が書かれています。具体的には、円盤 $i$ の周囲には $M_i$ 個の整数 $A_{i,1},\ A_{i,2},\ \dots\ A_{i,M_i}$ が書かれています。これらの整数には重複があるかもしれません。

また、円盤 $i$ を回してそこに球を転がすと球は $A_{i,1},\ A_{i,2},\ \dots\ A_{i,M_i}$ のいずれかが書かれたところに入ります。このとき、球が $A_{i, j}\ (1≦j≦M_i)$ に入る確率は $1/{M_i}$ です。

ある日、天才的な発想を持ついろはちゃんはこれらの円盤を使った遊びを思いつきました。それは次のようなものです。

まず、全ての円盤を回してそれぞれに球を転がす。
円盤 $1, 2, \dots N$ の順に、球が入ったところに書いてある整数をつなげて読む。
- 例えば、円盤が $3$ 個あり、球が入ったところに書いてある整数が円盤 $1, 2, 3$ 上でそれぞれ $11, 2, 717$ だった時は、 $112717$ を読み上げることになる。

いろはちゃんは読み上げられる整数の期待値が知りたくなりました。しかし、彼女はプログラマではなかったので期待値を求めることができませんでした。

あなたが優秀なプログラマであるかどうかは知りませんが、プログラマでないいろはちゃんのために期待値を求めてください。

ただし、期待値 (以降 $E$ とする) は小数になることがあるので、代わりに $E \times M_1 \times M_2 \times\ \dots\times\ M_N$ (この値は必ず整数になる) を $10^9+7$ で割った余りを求めてください。

制約

入力は全て整数である。
$1≦N≦200,000$
$1≦M_i\ (1≦i≦N)$
$M_1 + M_2 +\ \dots\ + M_N≦200,000$
$1≦A_{i, j}≦10^9\ (1≦i≦N, 1≦j≦M_i)$

入力

入力は以下の形式で与えられます。

 $N$ 
 $M_1\ A_{1, 1}\ A_{1, 2}\ \dots\ A_{1, M_1}$ 
 $M_2\ A_{2, 1}\ A_{2, 2}\ \dots\ A_{2, M_2}$ 
 $\vdots$ 
 $M_N\ A_{N, 1}\ A_{N, 2}\ \dots\ A_{N, M_N}$

出力

$E \times M_1 \times M_2 \times\ \dots\times\ M_N$ を $10^9+7$ で割った余りを出力してください。

入力例 1Copy

Copy

2
2 11 3
2 9 14

出力例 1Copy

Copy

この入力例では $2$ 個の円盤があり、それぞれ $11, 3$ と $9, 14$ が書かれています。

読み上げられる整数としてありうるものは $119, 1114, 39, 314$ の $4$ 個で、それぞれが等確率で出るので期待値は $\frac{119+1114+39+314}{4}=396.5$ になります。

答えは $396.5 \times 2 \times 2 = 1586$ となります。

入力例 2Copy

Copy

3
3 172 11 31
2 701 5
2 12 21

出力例 2Copy

Copy

43651798

読み上げられる整数としてありうるものは $11512, 11521, 31512, 31521, 172512, 172521, 1170112, 1170121, 3170112, 3170121, 17270112, 17270121$ です。

入力例 3Copy

Copy

3
1 1000000000
1 1000000000
1 1000000000

出力例 3Copy

Copy

999966190

この入力例では必ず $100000000010000000001000000000$ が読み上げられます。

$10^9+7$ で割った余りを求めることに注意してください。

入力例 4Copy

Copy

10
5 371094 2597554 69382646 8 99062422 
12 6553139 40789 2519037 81594 46824888 84 4912 27575435 2774 4060 331605 7438162 
5 36 65156096 71969458 2 221919 
7 738734 979629710 4841 7027881 6107446 267092962 634173170 
9 16252 6294622 6670 932636725 8 221842 111612 86053044 823517544 
3 589 70 347090831 
9 7853 6 3174 1 14675 42 10793760 777031 23350 
15 5143 23971 93 68615 4384503 3 5867 96099 81021 10506439 137503 43398308 52626 9895727 3 
6 9819 93 808 2025523 36 593697 
3 497384 767669 80690

出力例 4Copy

Copy

993753975