問題一覧 > 通常問題

No.2572 Midori on the grid

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 22
作問者 : ragna / テスター : deuteridayo 👑 AngrySadEight kusirakusira Magentor aplysiaSheep けんぴん
お気に入りにしたユーザー ProblemId : 10312 / 自分の提出
問題文最終更新日: 2023-12-01 12:58:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
緑以下コンテスト Extra (順位表) の他の問題:

Problem Statement

There are lattice points $(X,Y)$ $(0 \leq X \leq H,0 \leq Y \leq W)$ on a plane, and adjacent lattice points are connected by edges.
Midori is at point $(0,0)$ and wants to go to point $(H,W)$ by moving along the edges with the shortest distance.
You are given $Q$ integers $t_i$ $(1 \leq i \leq Q)$. For each of them, find the number of ways to choose Midori's route such that the route does not pass through any point on the line $y=x+t_i$.
Since the answer can be very large, output it modulo $998244353$.

Definition of adjacent lattice points

Lattice points $(A,B)$ and $(C,D)$ are adjacent if $\min (|A-C|,|B-D|)=0$ and $\max (|A-C|,|B-D|)=1$ hold.
For example, the lattice points adjacent to $(1,1)$ are the $4$ points $(0,1),(1,0),(2,1),(1,2)$.

Constraints

  • $ 1 \leq H,W \leq 10^5$
  • $ 1 \leq Q \leq 10^6$
  • $ -10^6 \leq t_i \leq 10^6 $
  • The line $y=x+t_i$ passes through neither point $(0,0)$ nor point $(H,W)$
  • All inputs are integers

Input

$H$ $W$ $Q$
$t_1$
$t_2$
$\vdots$
$t_Q$

Output

Output $Q$ lines. On the $i$-th line $(1 \leq i \leq Q)$, output the answer for $t_i$.

Sample

Sample 1
Input
2 1 1
1
Output
2

Since point $(0,1)$ cannot be passed through,

  • $(0,0)$ → $(1,0)$ → $(2,0)$ → $(2,1)$
  • $(0,0)$ → $(1,0)$ → $(1,1)$ → $(2,1)$
these $2$ routes are possible.

Sample 2
Input
200 100 5
24
129
-35
63
100
Output
481605547
514334971
0
19509670
514334970

Note that you should output the answer modulo $998244353$.

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