問題一覧 > 通常問題

No.2235 Line Up Colored Balls

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 : srjywrdnprktsrjywrdnprkt / テスター : t98slidert98slider
8 ProblemId : 9105 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-02 00:40:07

問題文

1, 2, , N1,~2,~\cdots,~NNN 種類の色があります。また、各 ii に対して色 ii で塗られたボールが xix_i 個入った袋があります。

あなたは袋に入ったボールがなくなるまで袋からボールを一つずつ取り出し一列に並べます。ただし、各ボールが取り出される確率は同様に確からしいものとします。

次に、異なる色のボールが隣り合っている部分で列を分割します。この操作によって得られる連続部分列の数を列の不連続度と呼びます。
この問題の制約下で、得られる列の不連続度の期待値は有理数になることが証明できますが、その値をmod  (109+7)\mod (10^9+7) で求めてください。

  • 有理数mod  (109+7)\mod (10^9+7)の定義

この問題の制約下では求める期待値を、互いに素な正整数 P, QP,~Q を用いて PQ\frac{P}{Q} のように既約分数で表したとき、QQ109+710^9+7 で割り切れないこと、および PQ×Rmod  (109+7)P \equiv Q\times R \mod (10^9+7) を満たす 00 以上 109+710^9+7 未満の整数 RR が一意に定まることが示せます。この RR を求めてください。

入力

NN
x1  xNx_1~\cdots~x_N

入力は全て整数で以下の制約を満たす。

  • 1N1051\leq N \leq 10^5
  • 1xi1 \leq x_i
  • i=1Nxi109\displaystyle \sum_{i=1}^N x_i \leq 10^{9}

出力

得られる列の不連続度の期待値をmod  (109+7)\mod (10^9+7) で出力してください。 最後に改行してください。

サンプル

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

11 のボールをa、色 22 のボールをbとします。これらをランダムに並べるとき、(aab, aba, baa)の3通りの列が等確率で得られます。
aabはaa bのように分割できるので不連続度は 22、abaはa b aのように分割できるので不連続度は 33、baaはb aaのように分割できるので不連続度は 22 となります。
以上より、不連続度の期待値は 73\frac{7}{3} となります。3×333333338mod  (109+7)73 \times 333333338\mod (10^9+7)\equiv 7 となるので 333333338333333338 が答えです。

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

全てのボールが同じ色なので不連続度は1にしかなり得ません。

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

全ての並べ方に対し不連続度は4となります。

サンプル4
入力
10
3 1 4 1 5 9 2 6 5 3
出力
384615422

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