問題一覧 > 通常問題

No.1299 Random Array Score

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 318
作問者 : nok0 / テスター : zkou Kite_kuma
30 ProblemId : 5473 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-26 15:02:21

問題文

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

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

  • 数列 A の要素を一様ランダムに 1 つ選択する。数列 A の全ての要素に、選択した要素の値を足し合わせる。

    • K 回の操作後の数列 A の要素の総和の期待値を求め、 mod998244353 で出力してください。

    より正確には、期待値が有理数、つまりある既約分数 PQ で表せること、更に R×Q≡P(mod998244353), 0≤R<998244353 を満たす整数 R が一意に定まることがこの問題の制約より証明できます。よって、この R を出力してください。

    制約

    • 入力は全て整数である。
    • 1≤N≤2×105
    • 0≤K≤1018
    • 0≤Ai≤109

    入力

    N K
A1 A2 … AN

    出力

    K 回の操作の後の数列 A の要素の総和の期待値を mod998244353 で出力してください。

    サンプル

    サンプル1
    入力
    3 1
1 2 3
    出力
    12

    操作で A1 が選択された場合、数列 A は (1+1,2+1,3+1)=(2,3,4) となります。

    同様に A2 が選択された場合、数列 A は (1+2,2+2,3+2)=(3,4,5)

    同様に A3 が選択された場合、数列 A は (1+3,2+3,3+3)=(4,5,6)

    となるので、 1 回の操作後の数列 A の総和の期待値は、 (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

    mod998244353 で出力してください。

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