No.2572 Midori on the grid
タグ : / 解いたユーザー数 20
作問者 :
ragna
/ テスター :
AngrySadEight
kusirakusira
Magentor
aplysiaSheep
けんぴん
問題文
平面上に格子点 $(X,Y)$ $(0 \leq X \leq H,0 \leq Y \leq W)$ があり、隣り合う格子点同士は辺でつながれています。
みどりさんは点 $(0,0)$ にいて、辺に沿って移動して最短距離で点 $(H,W)$ に行きたいです。
$Q$ 個の整数 $t_i$ $(1 \leq i \leq Q)$ が与えられるので、みどりさんが通る経路の選び方のうち、各直線 $y=x+t_i$ 上の点を通らない経路の選び方を求めてください。
ただし、答えは非常に大きくなる可能性があるため $998244353$ で割った余りを出力してください。
格子点が隣り合っているとは
格子点 $(A,B)$ と $(C,D)$ が隣り合っているとは $\min (|A-C|,|B-D|)=0$ かつ $\max (|A-C|,|B-D|)=1$ が成り立つことを指します。
例えば、 $(1,1)$ と隣り合っている格子点は $(0,1),(1,0),(2,1),(1,2)$ の$4$つです。
制約
- $ 1 \leq H,W \leq 10^5$
- $ 1 \leq Q \leq 10^6$
- $ -10^6 \leq t_i \leq 10^6 $
- 直線 $y=x+t_i$ は点 $(0,0)$ も点 $(H,W)$ も通らない
- 入力はすべて整数である
入力
$H$ $W$ $Q$ $t_1$ $t_2$ $\vdots$ $t_Q$
出力
$Q$ 行出力してください。 $i$ 行目 $(1 \leq i \leq Q)$ には $t_i$ に対する答えを出力してください。
サンプル
サンプル1
入力
2 1 1 1
出力
2
点 $(0,1)$ が通れないため、
- $(0,0)$ → $(1,0)$ → $(2,0)$ → $(2,1)$
- $(0,0)$ → $(1,0)$ → $(1,1)$ → $(2,1)$
サンプル2
入力
200 100 5 24 129 -35 63 100
出力
481605547 514334971 0 19509670 514334970
$998244353$ で割った余りを出力することに気を付けてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。