No.3403 Count 1210 Sequence
タグ : / 解いたユーザー数 42
作問者 :
yt142857
Germanium32
What is a 1210 Sequence?
A sequence of non-negative integers in which the absolute differences between adjacent terms are all equal is called a 1210 sequence.
For example, the sequence of non-negative integers $A = (1,2,1,0)$ is a 1210 sequence since it satisfies $|A_2 - A_1| = |A_3 - A_2| = |A_4 - A_3| = 1$.
Problem Statement
You are given positive integers $N,A$. Among all 1210 sequences, output the number of those with first term $A$, last term $0$, and length $N$, modulo $\mathrm{mod}998244353$.
Solve $T$ test cases.
Constraints
- $1 \le T \le 202500$
- $2 \le N \le 2025$
- $1 \le A \le 202500$
- All input values are integers.
Input
$T$ $testcase_1$ $testcase_2$ $\vdots$ $testcase_T$Here, $testcase_i$ denotes the information of the $i$-th test case, given in the following format.
$N\ A$
Output
Output $T$ lines.
On the $i$-th line, output the number of 1210 sequences satisfying the conditions, $\mathrm{mod} 998244353$.
End the output with a newline.
Sample
Sample 1
Input
5 4 1 2 202500 2025 1 2025 2 2025 1210
Output
2 1 0 977628774 969785723
For the $1$st test case, there are $2$ 1210 sequences of length $4$ with first term $1$ and last term $0$: $(1,2,1,0)$ $(1,0,1,0)$.
For the $2$nd test case, there is $1$ 1210 sequence of length $2$ with first term $202500$ and last term $0$: $(202500,0)$.
For the $3$rd test case, no 1210 sequence satisfies the conditions.
For the $4,5$th test cases, output the answer $\mathrm{mod}998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。