← 返回题目列表

AtCoder · agc054_e

E. 锯齿形突破

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

分数: 1200 点

问题陈述

给定的是整数 N 和 A。 求模数 998244353,排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) 满足以下条件。

  • P_1=A.
  • 可以重复以下操作,以便 P 只有两个元素。
    • 选择三个 连续 元素 x, y,和 z。 在这里, y<\min(x,z) or y>\max(x,z) 必须保留。 然后,擦除 y 来自 P.

解决 输入文件中的 T 测试用例。

约束

  • 1 \leq T \leq 5 \times 10^5
  • 3 \leq N \leq 10^6
  • 1 \leq A \leq N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个案例的格式如下:

N A

输出

打印每个测试用例的答案。


样本输入 1

8
3 1
3 2
3 3
4 1
4 2
4 3
4 4
200000 10000

示例输出 1

1
2
1
3
5
5
3
621235018

当 N=4,A=2,满足条件的一种排列是 P=(2,1,4,3)。 使其只有两个元素的一种方法如下。

  • 选择 (x,y,z)=(2,1,4) 擦除 1,导致 P=(2,4,3).
  • 选择 (x,y,z)=(2,4,3) 擦除 4,导致 P=(2,3).