No.2810 Have Another Go (Hard)
タグ : / 解いたユーザー数 29
作問者 :
highlighter
/ テスター :
Magentor
keisuke6
fact493
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もしくは右上の雲マークをクリックしてアカウントを作成してください。