Easy Random Product

2 secs 1024 MB

問題文

は以上以下の自然数のみから構成される長さの自然数配列を所持している。

その後、得られた配列をいくつかの空でない連続部分列に分け、各部分列をつの数字とみなした後にそれらの総積をとした。

例えば、の時

と分割すれば、の値はとなる。

なお、複数の分割が考えられる場合、はそのうちいずれかをランダムに選択するものとする。

最終的に得られるの期待値をで求めよ。

入力は以下の形式で与えられる。

n
S_1S_2...S_n

の期待値をで求めよ。

この条件のもとではなる自然数の組が存在することが証明できる。

この時を出力せよ。

・

3
123

この時、に対するの期待値は以下のようになる。

5
11111

250001034

15
314159265358979

26596503

登録なしで提出できます。

Go (1.14)