← 返回题目列表

Codeforces · 2125/E

E. 补集和

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

我们将一组整数称为 $$$Q$$$ a 一组互补和 如果可以通过以下操作获得:

  • 选择一个由 $$$m$$$ 个正整数组成的数组 $$$a$$$($$$m$$$ 是任意正整数);
  • 计算数组$$$a$$$中所有元素的总和$$$s$$$;
  • 对于数组中的每个元素 $$$a_{i}$$$,将数字 $$$s - a_{i}$$$ 添加到集合中,更正式地说,集合 $$$Q = \{s - a_{i}\;|\; 1 \le i \le m\}$$$。

请注意,$$$Q$$$ 不是多重集,这意味着其中的每个数字都是唯一的。例如,如果选择数组 $$$a = [1, 3, 3, 7]$$$,则 $$$s = 14$$$ 且 $$$Q = \{7, 11, 13\}$$$。

你的任务是计算不同的数量 组互补和 其中以下内容成立:

  • 该集合恰好包含 $$$n$$$ 个元素;
  • 集合中的每个元素都是从 $$$1$$$ 到 $$$x$$$ 的整数。

如果第一个集合中存在未包含在第二个集合中的元素,则两个集合被视为不同。

由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n, x \le 2 \cdot 10^{5}$$$)。

输入数据的附加约束:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$;
  • 所有测试用例的 $$$x$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,输出一个整数 - 问题的答案以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

5
1 7
2 5
3 10
27 31415
1000 999

输出
复制

7
10
34
605089068
0

注意

对于第一个测试用例,正好有 $$$7$$$ 合适的集合:

$$\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}$$

对于第二个测试用例,有 $$$10$$$ 合适的集合:

$$\{1, 2\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{3, 4\}, \{3, 5\}, \{4, 5\}$$