No.1299 Random Array Score
タグ : / 解いたユーザー数 316
作問者 :
nok0
/ テスター :
zkou
Kite_kuma
問題文
$N$ 要素の数列 $A$ が与えられます。数列 $A$ の $i$ 番目の要素は $A_i$ です。
ここで以下の操作をちょうど $K$ 回行います。
$K$ 回の操作後の数列 $A$ の要素の総和の期待値を求め、 $\bmod998244353$ で出力してください。
より正確には、期待値が有理数、つまりある既約分数 $\frac{P}{Q}$ で表せること、更に $R×Q≡P(\bmod 998244353),\ 0 \le R< 998244353$ を満たす整数 $R$ が一意に定まることがこの問題の制約より証明できます。よって、この $R$ を出力してください。
制約
- 入力は全て整数である。
- $1 \le N\le 2 × 10^5$
- $0 \le K \le 10^{18}$
- $0 \le A_i \le 10^9$
入力
$N\ K$ $A_1\ A_2\ \dots \ A_N$
出力
$K$ 回の操作の後の数列 $A$ の要素の総和の期待値を $\bmod 998244353$ で出力してください。
サンプル
サンプル1
入力
3 1 1 2 3
出力
12
操作で $A_1$ が選択された場合、数列 $A$ は $(1+1,2+1,3+1) = (2,3,4)$ となります。
同様に $A_2$ が選択された場合、数列 $A$ は $(1+2,2+2,3+2) = (3,4,5)$
同様に $A_3$ が選択された場合、数列 $A$ は $(1+3,2+3,3+3) = (4,5,6)$
となるので、 $1$ 回の操作後の数列 $A$ の総和の期待値は、 $\frac{(2 + 3 +4) + (3 + 4+5)+(4+5+6)}{3} = 12$ です。
サンプル2
入力
1 0 1
出力
1
操作が行われないこともあります。
サンプル3
入力
10 1000000000000000000 3 1 4 1 5 9 2 6 5 3
出力
461591775
$\bmod 998244353$ で出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。