問題一覧 > 通常問題

No.1299 Random Array Score

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 245
作問者 : nok0nok0 / テスター : zkouzkou Kite_kumaKite_kuma
26 ProblemId : 5473 / 出題時の順位表
問題文最終更新日: 2020-11-26 15:02:21

問題文

$N$ 要素の数列 $A$ が与えられます。数列 $A$ の $i$ 番目の要素は $A_i$ です。

ここで以下の操作をちょうど $K$ 回行います。

  • 数列 $A$ の要素を一様ランダムに $1$ つ選択する。数列 $A$ の全ての要素に、選択した要素の値を足し合わせる。
  • $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もしくは右上の雲マークをクリックしてアカウントを作成してください。