問題一覧 > 通常問題

No.2963 Mecha DESU

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : ねしん / テスター : 遭難者
0 ProblemId : 11521 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-16 14:48:35

ストーリー

惰弱な祭りに溺れる惰弱な正義

ドンレンジャーを一喝すべく

今、ここに俺、来てれり

恐れを知らぬものならば、かかってこい！

(太鼓の達人ナムコオリジナル「メカデス。」より引用)

か〇ちゃん「しゅやくのざはわたさないドン！ボクのあついえんそうをきくドーン！！」

(太鼓の達人3DS 『ちびドラゴンと不思議なオーブ』より引用)

問題文

今、数直線上に NN 体のゾンビが存在し、i=1,2,3,⋯ ,Ni=1,2,3,\cdots,N において座標 ii にゾンビが 11 体ずつ存在しています。

またカードが手札に MM 枚あり、ii 番目のカードに書かれている整数は AiA_i です。

今から次の行動を KK 回繰り返します。

  • ランダムにカードを手札から 11 枚取り出す。そのカードに書かれている整数を CC とする。原点から距離が CC 離れるごとに雷を落とす。雷を落とされたゾンビは感電する。

    • カードを選ぶ確率は等確率とし、行動ごとにカードを手札に戻すものとします。KK 回の操作の中で 11 回以上感電したゾンビの数の期待値を mod\text{mod} 998244353998244353 で求めてください。

    答えは分母が 998244353998244353 と互いに素の既約分数 PQ\frac{P}{Q} になるので、Qx≡PQx \equiv P (mod(\text{mod} 998244353)998244353) となる x(0≤x≤998244352)x(0 \leq x \leq 998244352) を求めてください。

    入力

    NN MM KK
A1A_1 A2A_2 ⋯\cdots AMA_M

  • 1≤N≤1061 \leq N \leq 10^6
  • 1≤M≤1051 \leq M \leq 10^5
  • 1≤K≤1051 \leq K \leq 10^5
  • 1≤Ai≤106 (1≤i≤M)1 \leq A_i \leq 10^6 \ (1 \leq i \leq M)

    • 出力

    感電しているゾンビの期待値を出力してください。

    サンプル

    サンプル1
    入力
    6 3 2
1 2 3
    出力
    110916044

    引いたカードが

    (1,1)(1,1) のときゾンビ 1,2,3,4,5,61,2,3,4,5,6 が、 　　　　　　

    (1,2)(1,2) のときゾンビ 1,2,3,4,5,61,2,3,4,5,6 が、 　　　　　　

    (1,3)(1,3) のときゾンビ 1,2,3,4,5,61,2,3,4,5,6 が、 　　　　　　

    (2,1)(2,1) のときゾンビ 1,2,3,4,5,61,2,3,4,5,6 が、 　　　　　　

    (2,2)(2,2) のときゾンビ 2,4,62,4,6 が、 　　　　　　

    (2,3)(2,3) のときゾンビ 2,3,4,62,3,4,6 が、 　　　　　　

    (3,1)(3,1) のときゾンビ 1,2,3,4,5,61,2,3,4,5,6 が、 　　　　　　

    (3,2)(3,2) のときゾンビ 2,3,4,62,3,4,6 が、 　　　　　　

    (3,3)(3,3) のときゾンビ 3,63,6 が、 　　　　　　

    感電しています。よって感電しているゾンビの数の期待値は 439\frac{43}{9} 体です。

    サンプル2
    入力
    5 1 1
6
    出力
    0

    11 体も感電しないこともあります。

    サンプル3
    入力
    49 7 5
1 3 5 7 7 9 21
    出力
    375551832

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