No.2503 Typical Path Counting Problem on a Grid
タグ : / 解いたユーザー数 32
作問者 :
emthrm
torisasami4
rniya
Problem Statement
You are given non-negative integers $n,m$.
Define a rectangular region $R$ on the two-dimensional plane by $R\coloneqq\lbrace (x,y)\mid 0 \leq x\leq n,\ 0\leq y\leq m\rbrace$.
Initially, suisen is at the point $(0, 0)\in R$.
suisen repeats the following action any number of times (possibly $0$ times) until reaching the point $(n, m)\in R$.
-
Let $(x, y)\in R$ be the point where suisen currently is. Choose $1$ of the following and perform it:
- Move to the point $(x + 1, y - 1)$.
- Move to the point $(x + 1, y)$.
- Move to the point $(x + 1, y + 1)$.
- Move to the point $(x, y + 1)$.
- Move to the point $(x - 1, y + 1)$.
However, moving to a point not contained in $R$ and moving to a point that has already been visited at least $1$ time are prohibited.
Find the number of ways suisen can act until reaching the point $(n, m)\in R$, and print it modulo $998244353$.
You are given $T$ test cases; solve the above problem for all of them.
Input
The input is given from standard input in the following format.
First, the number of test cases $T$ is given on line $1$ in the following format.
$T$
Line $i + 1\ (1\leq i\leq T)$ contains integers $n, m$ representing the $i$-th test case, in the following format.
$n\ m$
- All input values are integers.
- $1 \leq T\leq 2\times 10 ^ 4$
- $0 \leq n\leq 10 ^ 7$
- $0 \leq m\leq \textcolor{red}{10 ^ {18}}$
Output
Print $T$ lines. On line $i \ (1\leq i\leq T)$, print the answer to the $i$-th test case modulo $998244353$.
Print a newline after line $T$ of the output as well.
Sample
Sample 1
Input
4 1 1 0 0 10 20 10000000 1000000000000000000
Output
5 1 839227761 950133829
-
About test case 1
This represents $n = 1, m = 1$. The possible ways for suisen to act are the following $5$ ways. Therefore, print $5$.
- $(0, 0) \overset{\text{Action }2}{\longrightarrow} (1, 0) \overset{\text{Action }4}{\longrightarrow} (1,1)$
- $(0, 0) \overset{\text{Action }2}{\longrightarrow} (1, 0) \overset{\text{Action }5}{\longrightarrow} (0,1) \overset{\text{Action }2}{\longrightarrow} (1,1)$
- $(0, 0) \overset{\text{Action }3}{\longrightarrow} (1, 1)$
- $(0, 0) \overset{\text{Action }4}{\longrightarrow} (0, 1)\overset{\text{Action }2}{\longrightarrow} (1, 1)$
- $(0, 0) \overset{\text{Action }4}{\longrightarrow} (0, 1)\overset{\text{Action }1}{\longrightarrow} (1, 0) \overset{\text{Action }4}{\longrightarrow} (1, 1)$
Here, a path such as $(0, 0) \overset{\text{Action }2}{\longrightarrow} (1, 0) \overset{\text{Action }5}{\longrightarrow} (0,1) \overset{\text{Action }1}{\longrightarrow} (1,0) \overset{\text{Action }4}{\longrightarrow} (1,1)$ is not allowed, because it visits the point $(1,0)$ multiple times.
Also, a path such as $(0,0) \overset{\text{Action }1}{\longrightarrow} (1,-1) \overset{\text{Action }4}{\longrightarrow} (1,0) \overset{\text{Action }4}{\longrightarrow} (1,1)$ is not allowed, because it passes through the point $(1,-1)$, which is not contained in $R$.
-
About test case 2
This represents $n = 0, m = 0$. Not acting even $1$ time is also allowed, so the answer for this case is $1$.
-
About test case 3
Print the answer modulo $998244353$.
-
About test case 4
$m$ may not be representable in a 32 bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。