分数: 1100 点
问题陈述
求模数 998244353,字符串 S 长度 N 组成 A, B, C 使得以下值等于 K:
- 的(不一定是连续的)子序列的最大长度 S 不包含
ABC作为(不一定是连续的)子序列
你被给予 T 测试用例。解决它们中的每一个。
约束
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 10^6
- \max(0,N-100) \le K \le N
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N\ K
输出
输出 T 行。的 i第行 (1 \le i \le T) 应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
4 4 3 8 6 123 100 123456 123400
示例输出 1
9 462 741573397 255048895
对于第一个测试用例,例如, ACBC 满足条件。 ACBC 本身包含 ABC 作为子序列,并且 ACC 不包含 ABC 作为子序列,因此不包含的子序列的最大长度 ABC 作为子序列是 3。
满足条件的其他示例包括 AABC 和 ABCA.