No.1102 Remnants

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 197
作問者 :

eSeF / テスター :

37zigen

30 ProblemId : 4283 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-07-03 23:42:36

問題文

あなたは、正整数からなる長さ $N$ の数列 $A = (A_{1}, \dots, A_{N})$ を持っています。これに対して、以下の操作を $K$ 回行います。

・操作時点での数列を $B = (B_{1}, \dots, B_{M})$ とする。
　 $1 \leq l \leq r \leq M$ を満たす整数 $l, r$ を自由に選び、持っている数列を部分列 $(B_{l}, B_{l + 1}, \dots, B_{r})$ に置き換える。（添字は１から振り直す。）

$K$ 回の一連の操作のスコアを、操作が全て終了した時点での数列の要素の総和と定義します。
考えうる全ての操作手順についてスコアを求め、その合計を $10^{9} + 7$ で割ったあまりを出力してください。

なお、2つの操作手順が異なるとは、ある正整数 $i$ が存在して、 $i$ 回目の操作で選ぶ整数の組 $(l, r)$ が異なることを言います。

入力

 $N K$ 
 $A_{1} \dots A_{N}$

【制約】
・ $1 \leq N \leq 2 \times 10^{5}$
・ $0 \leq K \leq 10^{8}$
・ $1 \leq A_{i} \leq 10^{9}$
・入力は全て整数である。

出力

　答えを出力せよ。

サンプル

サンプル1

入力

2 2
3 4

出力

１回目の操作では、数列は $(3, 4), (3), (4)$ のいずれかになります。
２回目の操作では、 $(3, 4)$ からは $(3, 4), (3), (4)$ のいずれかに変化します。 $(3)$ からは $(3)$ 、 $(4)$ からは $(4)$ に変化します。
以上より、スコアの総和は $7 + 3 + 4 + 3 + 4 = 21$ です。

サンプル2

入力

4 0
1 2 3 4

出力

操作を行わないので、操作手順は１通りしかなく、スコアの総和は $10$ です。

サンプル3

入力

5 100000000
1000000000 999999999 888888888 777777777 666666666

出力

870870837

総和は非常に大きくなることがあるので、 $10^{9} + 7$ で割ったあまりを出力してください。

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