atcoder#DWACON6THPRELIMSB. Fusing Slimes
Fusing Slimes
配点 : 点
問題文
数直線上に 匹のスライムが並んでいます。 左から 番目のスライムは位置 にいます。
ここで、 が成立することが保証されます。
ニワンゴ君は操作を 回行います。 回目の操作は以下の手順からなります。
- 以上 以下の整数を等確率で選ぶ(これを とする)
- 左から 番目にいるスライムを右隣にいるスライムの位置まで移動させる
- その後、同じ位置にいる 匹のスライムを合体させ、 匹のスライムにする
回の操作によって、スライムが移動した距離の総和の期待値に をかけた値(これは整数になることが示せます)を で割ったあまりを求めてください。なお、合体後のスライムが移動した場合は 体のスライムの移動として数えます。
制約
- は整数
部分点
- であるようなテストケースすべてに正解すると、 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
3
1 2 3
5
- 確率 で最初に左から 番目のスライムが選ばれ、このときの移動距離の総和は となります。
- 確率 で最初に左から 番目のスライムが選ばれ、このときの移動距離の総和は となります。
- 移動距離の総和の期待値である に をかけた値である が答えとなります。
12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932
750927044
- 期待値の 倍を で割ったあまりを求めてください。