No.2572 Midori on the grid
タグ : / 解いたユーザー数 22
作問者 :
ragna
/ テスター :
kusirakusira
Magentor
aplysiaSheep
けんぴん
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)$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。