/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
数直線上に人 1, 人 2, 人 3 がいます。時刻 0 の時点で、人 1 は地点 A に、人 2 は地点 B に、人 3 は地点 C にいます。
ここで A, B, C はすべて整数で、A \equiv B \equiv C \pmod{2} が成り立ちます。
3 人は時刻 0 からランダムウォークを行います。詳しく説明すると、時刻 t ( t は非負整数 ) の時点で地点 x にいる人は、時刻 t+1 に地点 x-1 と地点 x+1 のいずれか一方に等確率で移動します。(すべての移動する方向の選択は、ランダムかつ独立です。)
このとき、時刻 0 以降で、時刻 T に初めて 3 人が同じ地点にいる状態になる確率を \text{mod } 998244353 で計算してください。
有理数 \text{mod }998244353 とは
求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。制約
- 0 \leq A, B, C, T \leq 10^5
- A \equiv B \equiv C \pmod{2}
- A, B, C, T は整数
入力
入力は以下の形式で標準入力から与えられる。
A B C T
出力
時刻 T に初めて 3 人が同じ地点にいる状態になる確率を \text{mod } 998244353 で計算して、答えを出力せよ。
入力例 1
1 1 3 1
出力例 1
873463809
時刻 1 に初めて 3 人が同じ地点にいる状態になる確率は \frac{1}{8} です。873463809 \times 8 \equiv 1 \pmod{998244353} なので 873463809 を出力します。
入力例 2
0 0 0 0
出力例 2
1
時刻 0 の時点ですでに 3 人が同じ地点にいる場合もあります。
入力例 3
0 2 8 9
出力例 3
744570476
入力例 4
47717 21993 74147 76720
出力例 4
844927176
Score : 600 points
Problem Statement
On a number line are person 1, person 2, and person 3. At time 0, person 1 is at point A, person 2 is at point B, and person 3 is at point C.
Here, A, B, and C are all integers, and A \equiv B \equiv C \pmod{2}.
At time 0, the three people start random walks. Specifically, a person that is at point x at time t (t is a non-negative integer) moves to point (x-1) or point (x+1) at time (t+1) with equal probability. (All choices of moves are random and independent.)
Find the probability, modulo 998244353, that it is at time T that the three people are at the same point for the first time.
What is rational number modulo 998244353?
We can prove that the sought probability is always a rational number. Moreover, under the Constraints of this problem, when the value is represented as \frac{P}{Q} by two coprime integers P and Q, we can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find such R.Constraints
- 0 \leq A, B, C, T \leq 10^5
- A \equiv B \equiv C \pmod{2}
- A, B, C, and T are integers.
Input
The input is given from Standard Input in the following format:
A B C T
Output
Find the probability, modulo 998244353, that it is at time T that the three people are at the same point for the first time, and print the answer.
Sample Input 1
1 1 3 1
Sample Output 1
873463809
The three people are at the same point for the first time at time 1 with the probability \frac{1}{8}. Since 873463809 \times 8 \equiv 1 \pmod{998244353}, 873463809 should be printed.
Sample Input 2
0 0 0 0
Sample Output 2
1
The three people may already be at the same point at time 0.
Sample Input 3
0 2 8 9
Sample Output 3
744570476
Sample Input 4
47717 21993 74147 76720
Sample Output 4
844927176