← 返回题目列表

AtCoder · abc463_g

G. 随机游走距离

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

分数: 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}.