問題一覧 > 通常問題

No.2572 Midori on the grid

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : ragnaragna / テスター : deuteridayodeuteridayo 👑 AngrySadEightAngrySadEight kusirakusirakusirakusira MagentorMagentor aplysiaSheepaplysiaSheep けんぴんけんぴん
1 ProblemId : 10312 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-01 12:58:32

問題文

平面上に格子点 (X,Y)(X,Y) (0XH,0YW)(0 \leq X \leq H,0 \leq Y \leq W) があり、隣り合う格子点同士は辺でつながれています。
みどりさんは点 (0,0)(0,0) にいて、辺に沿って移動して最短距離で点 (H,W)(H,W) に行きたいです。
QQ 個の整数 tit_i (1iQ)(1 \leq i \leq Q) が与えられるので、みどりさんが通る経路の選び方のうち、各直線 y=x+tiy=x+t_i 上の点を通らない経路の選び方を求めてください。
ただし、答えは非常に大きくなる可能性があるため 998244353998244353 で割った余りを出力してください。

格子点が隣り合っているとは

格子点 (A,B)(A,B)(C,D)(C,D) が隣り合っているとは min(AC,BD)=0\min (|A-C|,|B-D|)=0 かつ max(AC,BD)=1\max (|A-C|,|B-D|)=1 が成り立つことを指します。
例えば、 (1,1)(1,1) と隣り合っている格子点は (0,1),(1,0),(2,1),(1,2)(0,1),(1,0),(2,1),(1,2)44つです。

制約

  • 1H,W105 1 \leq H,W \leq 10^5
  • 1Q106 1 \leq Q \leq 10^6
  • 106ti106 -10^6 \leq t_i \leq 10^6
  • 直線 y=x+tiy=x+t_i は点 (0,0)(0,0) も点 (H,W)(H,W) も通らない
  • 入力はすべて整数である

入力

HH WW QQ
t1t_1
t2t_2
\vdots
tQt_Q

出力

QQ 行出力してください。 ii 行目 (1iQ)(1 \leq i \leq Q) には tit_i に対する答えを出力してください。

サンプル

サンプル1
入力
2 1 1
1
出力
2

(0,1)(0,1) が通れないため、

  • (0,0)(0,0)(1,0)(1,0)(2,0)(2,0)(2,1)(2,1)
  • (0,0)(0,0)(1,0)(1,0)(1,1)(1,1)(2,1)(2,1)
22 通りの経路が考えられます。

サンプル2
入力
200 100 5
24
129
-35
63
100
出力
481605547
514334971
0
19509670
514334970

998244353998244353 で割った余りを出力することに気を付けてください。

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