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