atcoder#DWACON6THPRELIMSB. Fusing Slimes
Fusing Slimes
题目描述
数直線上に 匹のスライムが並んでいます。 左から 番目のスライムは位置 にいます。
ここで、$ 1\ \leq\ x_1\ <\ x_2\ <\ \ldots\ <\ x_N\ \leq\ 10^{9} $ が成立することが保証されます。
ニワンゴ君は操作を 回行います。 回目の操作は以下の手順からなります。
- 以上 以下の整数を等確率で選ぶ(これを とする)
- 左から 番目にいるスライムを右隣にいるスライムの位置まで移動させる
- その後、同じ位置にいる 匹のスライムを合体させ、 匹のスライムにする
回の操作によって、スライムが移動した距離の総和の期待値に をかけた値(これは整数になることが示せます)を で割ったあまりを求めてください。なお、合体後のスライムが移動した場合は 体のスライムの移動として数えます。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを出力せよ。
题目大意
有 个史莱姆站在一条数轴上,从左数第 个史莱姆在数轴上的位置为 。
保证 。
Niwango将要执行 次操作。第 次操作由以下过程组成:
- 以相同的概率选择一个 中的整数 。
- 把从左数第 个史莱姆移动到它右边的第一个史莱姆处。
- 将两个在相同位置的史莱姆融合成一个史莱姆。
请求出所有的史莱姆经过的总距离与 的乘积在对 取模意义下的值(可以证明这个值是一个整数)。如果一个通过融合生成的史莱姆发生移动,我们只把它看成一个史莱姆。
3
1 2 3
5
12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932
750927044
提示
制約
- $ 1\ \leq\ x_1\ <\ x_2\ <\ \ldots\ <\ x_N\ \leq\ 10^{9} $
- は整数
部分点
- であるようなテストケースすべてに正解すると、 点が与えられる。
Sample Explanation 1
- 確率 で最初に左から 番目のスライムが選ばれ、このときの移動距離の総和は となります。 - 確率 で最初に左から 番目のスライムが選ばれ、このときの移動距離の総和は となります。 - 移動距離の総和の期待値である に をかけた値である が答えとなります。
Sample Explanation 2
- 期待値の 倍を で割ったあまりを求めてください。