No.2807 Have Another Go (Easy)
タグ : / 解いたユーザー数 66
作問者 :
![highlighter](https://pbs.twimg.com/profile_images/1707374069132439552/b_BWx6c8.png)
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![keisuke6](https://pbs.twimg.com/profile_images/1675785204974354432/k3Bvkvyj.jpg)
![fact493](https://pbs.twimg.com/profile_images/1641449306531192836/GjfyenV1.jpg)
注意
この問題は Have Another Go (Hard) の制約緩和版です。Hard版との違いは、$6\leq N\leq 5 \times 10^{5}$ 、$M=2$ であることです。
ストーリー
必ずしもこの項を読む必要はない。
tfl君は $N$ 個のマスを $1$ 周して落ちているコインを集めるすごろくで遊んでいます。しかし...
tfl君「$1$ 周したけど全然コインが取れなかった...」
highlighterはかせ「それじゃあ、$2$ 周してもいいことにしよう。これで億万長者間違いなしじゃ!」
tfl君「$2$ 周じゃあんま変わらないと思うんだけど...」
highlighterはかせ「もっと多くすると通り数を求めるのが大変じゃろう」
tfl君「え、いや通り数を求めるつもりはないんだけど!?」
問題文
tfl君は次のようなゲームで遊んでいます。
- 変数 $X$ と空の配列 $Y$ を用意する。はじめ $X$ の値は $0$ に等しい。
-
以下の一連の操作を行う。
- $X$ を $Y$ の末尾に付け加える。
- $1$ 以上 $6$ 以下の整数が等確率で出るサイコロを振る。
- $X$ にサイコロで出た目の数を加える。
- $X \geq NM$ なら操作を終える。そうでないなら、またこの操作を繰り返す。
ただし、この問題では $M=2$ です。
$i=1,2,\ldots k$ について、以下の問いに答えてください。
ただし、サイコロを振る操作は毎回独立です。
制約
- $6 \leq N \leq 5 \times 10^{5}$
- $M=2$
- $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
入力
7 2 4 1 2 3 4
出力
29503 29564 29684 29920
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。