問題一覧 > 通常問題

No.2810 Have Another Go (Hard)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : highlighterhighlighter / テスター : hirayuu_ychirayuu_yc tfltkpctfltkpc MagentorMagentor penguin8331penguin8331 keisuke6keisuke6 warabi0906warabi0906 zeta7532zeta7532 Yoyoyo8128Yoyoyo8128 fact493fact493
0 ProblemId : 11053 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-12 20:56:10

注意

この問題は Have Another Go (Easy) の制約強化版です。Easy版との違いは、$6 \leq N\leq 10^{9}$$1 \leq M \leq 10^{9}$ であることです。

ストーリー

必ずしもこの項を読む必要はない。

tfl君はとあるすごろくを $2$ 周しましたが...

tfl君「たった $2$ 周じゃコインが獲得できないぃぃ...」

highlighterはかせ「仕方ないのぉ。$M$ 周できるチャンスをやる。 $M$ は最大で $10^{9}$ にもなるぞい!これで文句ないじゃろ!(笑)」

tfl君「いやさすがに長すぎるだろ」

tfl君「...これ $M$ の下限 $1$ だから最悪さっきより悪化するのでは?」

highlighterはかせ「作問の都合じゃ、黙るがよい」

問題文

tfl君は次のようなゲームで遊んでいます。

  • 変数 $X$ と空の配列 $Y$ を用意する。はじめ $X$ の値は $0$ に等しい。
  • 以下の一連の操作を行う。
    • $X$ を $Y$ の末尾に付け加える。
    • $1$ 以上 $6$ 以下の整数が等確率で出るサイコロを振る。
    • $X$ にサイコロで出た目の数を加える。
    • $X \geq NM$ なら操作を終える。そうでないなら、またこの操作を繰り返す。

$i=1,2,\ldots k$ について、以下の問いに答えてください。

  • 操作終了後、ある $Y$ の要素 $y$ が存在して、 $y \equiv C_{i} \pmod N$ となるようなサイコロの目の出方の通り数を求め、 $998244353$ で割った余りを出力してください。
  • ただし、サイコロを振る操作は毎回独立です。

    制約

    • $6 \leq N \leq 10^{9}$
    • $1\leq M\leq 10^{9}$
    • $1 \leq k \leq 5000$
    • $1 \leq C_{i} \lt N$
    • 入力はすべて整数

    入力

    入力は以下の形式で標準入力から与えられる。
    $N~~~M~~~k$
    $C_{1} ~~~ C_{2} ~ \ldots ~ C_{k}$
    

    出力

    $k$ 行出力せよ。 $i$ 行目には、 $C_{i}$ に対する答えを $998244353$ で割った余りを出力せよ。

    サンプル

    サンプル1
    入力
    100 100 5
    1 2 3 4 5
    出力
    138959755
    683208998
    780270567
    968245045
    696325744

    答えを $998244353$ で割った余りを求めることに注意してください。

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