問題一覧 > 通常問題

No.2963 Mecha DESU

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

ストーリー

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

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

今、ここに俺、来てれり

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

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

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

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

問題文

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

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

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

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

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

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

    入力

    $N$ $M$ $K$
    $A_1$ $A_2$ $\cdots$ $A_M$
    

  • $1 \leq N \leq 10^6$
  • $1 \leq M \leq 10^5$
  • $1 \leq K \leq 10^5$
  • $1 \leq A_i \leq 10^6 \ (1 \leq i \leq M)$
  • 出力

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

    サンプル

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

    引いたカードが

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

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

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

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

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

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

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

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

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

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

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

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

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

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