分数: 600 点
问题陈述
给你一个正整数 N 和一个整数 X.
高桥在坐标 数轴上的 0 。 他现在将执行以下动作 N 次:
- 处于坐标时 x,选择坐标 x-1 或坐标 x+1 以相同的概率移动到那里。
目的地的选择 N 动作都是独立的。 让 x' 毕竟是坐标 N 移动。求期望值,取模 998244353,属于 |x'-X|.
你被给予 T 测试用例;解决它们中的每一个。
期望值模的定义 998244353
可以证明,求的期望值始终是有理数。而且,在这个问题的约束下,可以证明当表示为不可约分数时 \frac{P}{Q},我们有 Q {{}\not\equiv{}} 0 \pmod{998244353}。因此,存在一个唯一的整数 R 满意 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。找到这个 R.
约束
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 2 \times 10^5
- |X| \leq 2 \times 10^5
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个 \mathrm{case}_i 是 i-第一个测试用例,以以下格式给出:
N X
输出
输出 T 行。 的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
样本输入 1
5 3 2 6 4 2026 -620 12345 67890 98765 -43210
示例输出 1
748683267 935854085 270602660 67890 844852181
对于第一个测试用例,高桥最终位于坐标 -3 有概率 \frac{1}{8},在坐标处 -1 有概率 \frac{3}{8},在坐标处 1 有概率 \frac{3}{8},并且在坐标处 3 有概率 \frac{1}{8}。 因此,期望值 |x'-X| is \frac{1}{8}\cdot|{-3}-2|+\frac{3}{8}\cdot|{-1}-2|+\frac{3}{8}\cdot|1-2|+\frac{1}{8}\cdot|3-2|=\frac{9}{4}.