/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
正整数 N および整数 X が与えられます。
高橋君が数直線上の座標 0 にいます。 高橋君はこれから N 回、以下の移動を行います。
- 座標 x にいるとき、座標 x-1 または座標 x+1 のどちらかを等確率で選び、そこに移動する。
ただし N 回の移動での移動先の選択はすべて独立です。 N 回の移動を全て終えた後の座標を x' とします。|x'-X| の期待値を \bmod{998244353} で求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
期待値 \bmod{998244353} の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q {{}\not\equiv{}} 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この 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
1 番目のテストケースについて、最終的に高橋君は確率 \frac{1}{8} で座標 -3 に、確率 \frac{3}{8} で座標 -1 に、確率 \frac{3}{8} で座標 1 に、確率 \frac{1}{8} で座標 3 にいます。 したがって |x'-X| の期待値は \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} です。
Score : 600 points
Problem Statement
You are given a positive integer N and an integer X.
Takahashi is at coordinate 0 on a number line. He will now perform the following move N times:
- When at coordinate x, choose coordinate x-1 or coordinate x+1 with equal probability and move there.
The choices of destination across the N moves are all independent. Let x' be the coordinate after all N moves. Find the expected value, modulo 998244353, of |x'-X|.
You are given T test cases; solve each of them.
Definition of expected value modulo 998244353
It can be proved that the sought expected value is always a rational number. Moreover, under the constraints of this problem, it can be proved that when expressed as an irreducible fraction \frac{P}{Q}, we have Q {{}\not\equiv{}} 0 \pmod{998244353}. Therefore, there is a unique integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Find this R.
Constraints
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 2 \times 10^5
- |X| \leq 2 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each \mathrm{case}_i is the i-th test case and is given in the following format:
N X
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
5 3 2 6 4 2026 -620 12345 67890 98765 -43210
Sample Output 1
748683267 935854085 270602660 67890 844852181
For the first test case, Takahashi ends up at coordinate -3 with probability \frac{1}{8}, at coordinate -1 with probability \frac{3}{8}, at coordinate 1 with probability \frac{3}{8}, and at coordinate 3 with probability \frac{1}{8}. Thus, the expected value of |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}.