問題一覧 > 通常問題

No.2810 Have Another Go (Hard)

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 29
作問者 : highlighter / テスター : hirayuu_yc tfltkpc Magentor penguin8331 keisuke6 warabi0906 zeta7532 Yoyoyo8128 fact493
お気に入りにしたユーザー ProblemId : 11053 / 自分の提出
問題文最終更新日: 2025-09-27 11:51:15
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 (Easy) with stronger constraints. The difference from the Easy version is that $6 \leq N\leq 10^{9}$ and $1 \leq M \leq 10^{9}$.

Story

You do not necessarily have to read this section.

tfl-kun went around a certain sugoroku board $2$ times, but...

tfl-kun: "I can't get any coins with just $2$ laps..."

Professor highlighter: "It can't be helped. I'll give you a chance to go around $M$ times. $M$ can be as large as $10^{9}$! You can't complain about that! (lol)"

tfl-kun: "No, that's way too long."

tfl-kun: "...Wait, the lower bound of $M$ is $1$, so in the worst case isn't this even worse than before?"

Professor highlighter: "That's just how the problem had to be set. Hold your tongue."

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 an integer between $1$ and $6$, inclusive, with equal probability.
    • Add the number shown on the die to $X$.
    • If $X \geq NM$, finish the operations. Otherwise, repeat these operations again.

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

  • Find the number of sequences of die rolls such that, after the operations finish, there exists an element $y$ of $Y$ with $y \equiv C_{i} \pmod N$, and output it modulo $998244353$.

Here, each die roll is independent.

Constraints

  • $6 \leq N \leq 10^{9}$
  • $1\leq M\leq 10^{9}$
  • $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

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

Sample

Sample 1
Input
100 100 5
1 2 3 4 5
Output
138959755
683208998
780270567
968245045
696325744

Note that you must find the answer modulo $998244353$.

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