問題一覧 > 通常問題

No.3403 Count 1210 Sequence

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : yu23578 / テスター : yt142857 GaLLium Germanium32
お気に入りにしたユーザー ProblemId : 12893 / 自分の提出
問題文最終更新日: 2025-12-09 21:39:35
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
Advent Calendar Contest 2025 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。