检查 - 代码源竞赛平台

题目描述

一条笔直的巡检线上，每个整数坐标处都有一个检查点。巡检员从坐标 $0$ 出发，开始时只有坐标 $0$ 处的检查点已经访问过。

巡检员要恰好跳跃 $n$ 次，每次可以自由选择向左或向右。选定方向后，他会跳到该方向上距离当前位置最近的、尚未访问过的整数坐标，并立即将落点标记为已经访问。跳跃途中可以跨过已经访问的检查点。

一次跳跃的长度为起点与落点坐标差的绝对值。给定 $n$ 和 $K$，求总跳跃长度恰好为 $K$ 的方向序列有多少种，答案对 $998244353$ 取模。

只要某一步选择的方向不同，就视为不同的方向序列，即使最终位置或总路程相同也要分别计数。若不存在符合要求的方向序列，答案为 $0$。

输入格式

第一行包含一个正整数 $n$ 和一个非负整数 $K$，分别为跳跃次数和要求的总跳跃长度。

输出格式

输出一个非负整数，表示总跳跃长度恰好为 $K$ 的方向序列数量对 $998244353$ 取模后的结果。

样例

2 3

2

4 7

4

3 7

0

样例解释

样例 1：“左、右”依次到达 $-1,1$，总路程为 $1+2=3$；“右、左”也满足要求。另两种方向序列的总路程都是 $2$。

样例 2：合法方向序列为“右、右、右、左”“右、左、右、右”，以及它们左右互换后的两种序列。前两种序列的落点分别为 $(1,2,3,-1)$ 和 $(1,-1,2,3)$，总路程均为 $7$。

样例 3：三次跳跃的长度分别不超过 $1,2,3$，总路程不超过 $6$，因此不存在符合要求的序列。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$
$1$	$30$	$20$
$2$	$20$	$40$
$3$	$50$	$100$

对于 $100\%$ 的数据，$1\le n\le100$，$0\le K\le10^4$。