No.2235 Line Up Colored Balls
タグ : / 解いたユーザー数 83
作問者 :
srjywrdnprkt
/ テスター :
t98slider
問題文
$1,~2,~\cdots,~N$ の $N$ 種類の色があります。また、各 $i$ に対して色 $i$ で塗られたボールが $x_i$ 個入った袋があります。
あなたは袋に入ったボールがなくなるまで袋からボールを一つずつ取り出し一列に並べます。ただし、各ボールが取り出される確率は同様に確からしいものとします。
次に、異なる色のボールが隣り合っている部分で列を分割します。この操作によって得られる連続部分列の数を列の不連続度と呼びます。
この問題の制約下で、得られる列の不連続度の期待値は有理数になることが証明できますが、その値を$\mod (10^9+7)$ で求めてください。
- 有理数$\mod (10^9+7)$の定義
この問題の制約下では求める期待値を、互いに素な正整数 $P,~Q$ を用いて $\frac{P}{Q}$ のように既約分数で表したとき、$Q$ が $10^9+7$ で割り切れないこと、および $P \equiv Q\times R \mod (10^9+7)$ を満たす $0$ 以上 $10^9+7$ 未満の整数 $R$ が一意に定まることが示せます。この $R$ を求めてください。
入力
$N$ $x_1~\cdots~x_N$
入力は全て整数で以下の制約を満たす。
- $1\leq N \leq 10^5$
- $1 \leq x_i$
- $\displaystyle \sum_{i=1}^N x_i \leq 10^{9}$
出力
得られる列の不連続度の期待値を$\mod (10^9+7)$ で出力してください。 最後に改行してください。
サンプル
サンプル1
入力
2 2 1
出力
333333338
色 $1$ のボールをa、色 $2$ のボールをbとします。これらをランダムに並べるとき、(aab, aba, baa)の3通りの列が等確率で得られます。
aabはaa bのように分割できるので不連続度は $2$、abaはa b aのように分割できるので不連続度は $3$、baaはb aaのように分割できるので不連続度は $2$ となります。
以上より、不連続度の期待値は $\frac{7}{3}$ となります。$3 \times 333333338\mod (10^9+7)\equiv 7$ となるので $333333338$ が答えです。
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。