問題一覧 > 通常問題

No.2807 Have Another Go (Easy)

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 73
作問者 : tfltkpc / テスター : hirayuu_yc highlighter Magentor keisuke6 Yoyoyo8128 zeta7532 silv723 fact493
お気に入りにしたユーザー ProblemId : 11074 / 自分の提出
問題文最終更新日: 2024-07-12 20:53:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 436 ('09 Contest 002 day1) (順位表) の他の問題:

Note

This problem is a version of Have Another Go (Hard) with relaxed constraints. The differences from the Hard version are that $6\leq N\leq 5 \times 10^{5}$ and $M=2$.

Story

You do not necessarily need to read this section.

tfl-kun is playing a sugoroku game in which he goes around $N$ squares for $1$ lap, collecting the coins lying on them. However...

tfl-kun: "I went around $1$ lap, but I hardly got any coins..."

Professor highlighter: "Well then, let's allow you to go around $2$ laps. With this, you're sure to become a billionaire!"

tfl-kun: "I don't think $2$ laps will change much, though..."

Professor highlighter: "Any more than that, and counting the number of ways would be tough, wouldn't it?"

tfl-kun: "Huh? Wait, I wasn't planning on counting the number of ways!?"

Problem Statement

tfl-kun is playing the following game.

  • Prepare a variable $X$ and an empty array $Y$. Initially, the value of $X$ is equal to $0$.
  • Perform the following series of operations.
    • Append $X$ to the end of $Y$.
    • Roll a die that shows each integer from $1$ to $6$ with equal probability.
    • Add the number shown on the die to $X$.
    • If $X \geq NM$, end the operations. Otherwise, repeat these operations.

Note that $M=2$ in this problem.

For each $i=1,2,\ldots k$, answer the following question.

  • Find the number of sequences of die rolls such that, after the operations end, there exists an element $y$ of $Y$ with $y \equiv C_{i} \pmod N$, and print it modulo $998244353$.
  • Here, each die roll is independent.

    Constraints

    • $6 \leq N \leq 5 \times 10^{5}$
    • $M=2$
    • $1 \leq k \leq 5000$
    • $1 \leq C_{i} \lt N$
    • All inputs are integers.

    Input

    The input is given from standard input in the following format.
    $N~~~M~~~k$
    $C_{1} ~~~ C_{2} ~ \ldots ~ C_{k}$
    

    Output

    Print $k$ lines. On the $i$-th line, print the answer for $C_{i}$ modulo $998244353$.

    Sample

    Sample 1
    Input
    7 2 4
    1 2 3 4
    Output
    29503
    29564
    29684
    29920

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