← 返回题目列表

Codeforces · 1942/E

E. 农场游戏

中文机器翻译题面 查看原题

农夫 Nhoj 带着他的奶牛来到农夫​​约翰的农场玩游戏! FJ 的农场可以通过一条数轴进行建模,其中墙位于点 $$$0$$$ 和 $$$l + 1$$$ 处。农场里有 $$$2n$$$ 头奶牛,其中 $$$n$$$ 属于 FJ,其余 $$$n$$$ 属于 FN。他们将每头奶牛放置在不同的点,FJ 的奶牛和 FN 的奶牛都不会相邻。如果两头牛之间没有其他牛,则它们是相邻的。

形式上,如果 $$$a_1, a_2, \ldots, a_n$$$ 代表 FJ 的奶牛的位置,而 $$$b_1, b_2, \ldots, b_n$$$ 代表 FN 的奶牛的位置,则 $$$0 < a_1 < b_1 < a_2 < b_2 < \ldots < a_n < b_n < l + 1$$$ 或 $$$0 < b_1 < a_1 < b_2 < a_2 < \ldots < b_n < a_n < l + 1$$$。

在一步操作中,农民选择一个数字 $$$k$$$ $$$(1 \leq k \leq n)$$$ 和一个方向(左或右)。然后,该农民选择他的 $$$k$$$ 头奶牛,并将它们朝着所选方向移动一个位置。农民不能将他的任何牛移到墙上或另一个农民的牛身上。如果一个农民不能移动任何奶牛,那么这个农民就输了。 FJ 开始游戏,进行第一个回合。

给定 $$$l$$$ 和 $$$n$$$,找到如果两个农民都发挥最佳状态,Farmer John 可能获胜的游戏配置数量。游戏可能会无限期地继续下去,没有农民获胜。如果存在任何 $$$i$$$ 使得 $$$a_i$$$ 或 $$$b_i$$$ 不同,则配置与另一个配置不同。输出对 $$$998\,244\,353$$$ 取模的答案。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例包含两个整数 $$$l$$$ 和 $$$n$$$ ($$$2 \leq l \leq 10^6, 1 \leq n \leq \lfloor \frac{l}{2} \rfloor$$$) - 数轴的长度和每个农民将放置的奶牛数量。

保证所有测试用例的$$$l$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出一个整数:如果两个农民都发挥最佳,则 Farmer John 获胜的游戏配置数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3
2 1
3 1
420 69

输出 #1

0
2
870279412

注意

设 J 表示 FJ 的牛,N 表示 FN 的牛,_ 表示空白区域。

对于第一个测试用例,两种可能的配置是 JN 或 NJ。在这两种情况下,由于FJ都先回合并且无法做出任何动作,所以他无法获胜。

对于第二种情况,FJ 获胜有两种可能的配置:N_J 和 J_N。