No.1336 Union on Blackboard
タグ : / 解いたユーザー数 209
作問者 :
蜜蜂
/ テスター :
Mitarushi
問題文
$N$個の整数$A_1,A_2, \cdots\ ,A_N$が黒板に書かれています。
あなたは以下の操作を$N-1$回行い、黒板に書かれた数を$1$つにします。
・黒板に書かれた数を一様ランダムに$2$つ選ぶ。この$2$つの数は異なる場所に書かれている必要がある。そして、選んだ$2$つの数の和と積を足し合わせた数を黒板に新しく書き込み、選んだ$2$つの数を黒板から消す。
$N-1$回の操作後、最後に残った$1$つの数の期待値を求めてください。
この際、期待値が$0$以上の有理数となることが保証されます。
期待値が$0$の場合は$0$と出力してください。
そうでない場合、期待値は$1$以上の整数$P,Q$を用いて既約分数$\frac{P}{Q}$と表せること、さらに$X \times Q \equiv P(\rm{mod} 10^9+7)$かつ$0 \leq X < 10^9+7$となる整数$X$が一意に存在することがこの問題の制約より証明できるので、そのような$X$を出力して下さい。
$T$個のテストケースが与えられるので、全てのテストケースについて答えてください。
入力
入力の$1$行目は以下の通りです。$T$そして、$T$個のテストケースが続きます。これらはそれぞれ以下の形式で与えられます。
$N$ $A_1\ A_2\ \cdots\ A_N$
・$1 \leq T \leq 100$
・$2 \leq N \leq 100$
・$0 \leq A_i \leq 200 (1 \leq i \leq N)$
・入力は全て整数
出力
$T$行出力してください。$i$行目には$i$番目のテストケースの場合の期待値を$\rm{mod} 10^9+7$で出力し、改行してください。
サンプル
サンプル1
入力
2
3
1 1 0
2
1 1
出力
3
3
$1$番目のテストケースについて、最後に残った数はそれぞれ確率$\frac{1}{3}$で次のいずれかになります。
・最初に$A_1,A_2$を選ぶ場合:$1$回目の操作後$3,0$が黒板に残り、$2$回目の操作後には$(3+0)+(3 \times 0)=3$が残ります。
・最初に$A_1,A_3$を選ぶ場合:$1$回目の操作後$1,1$が黒板に残り、$2$回目の操作後には$(1+1)+(1 \times 1)=3$が残ります。
・最初に$A_2,A_3$を選ぶ場合:$1$回目の操作後$1,1$が黒板に残り、$2$回目の操作後には$(1+1)+(1 \times 1)=3$が残ります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。