102897: [Atcoder]ABC289 Ex - Trio
Description
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
Input
题意翻译
一个数轴上有 $3$ 个人，分别在点 $A,B,C$ 上，且 $A,B,C$ 奇偶性相同。这 $3$ 个人从时刻 $0$ 开始移动，每经过一个时刻，一个人就会从原先所在的位置 $x$ 走到位置 $x+1$ 或 $x-1$，问在 $T$ 时刻有多大的概率 $3$ 个人走到相同的位置，答案对 $998244353$ 取模，$0\le A,B,C,T\le 10^5$。Output
问题描述
在数轴上有1号人、2号人和3号人。在时间0时，1号人在点A，2号人在点B，3号人在点C。
其中，A、B和C都是整数，且A ≡ B ≡ C（mod 2）。
在时间0时，三个人开始随机行走。具体来说，一个在时间t（t是一个非负整数）位于点x的人在时间（t+1）移动到点（x-1）或点（x+1）的概率相等。 （所有的移动选择都是随机且独立的。）
求以998244353为模的商，表示三个人首次同时在同一个点上的时间的概率。
什么是998244353的有理数？
我们可以证明所求概率总是有理数。 此外，在本问题的约束下，当该值用两个互素整数P和Q表示为$\frac{P}{Q}$时，我们可以证明存在一个唯一的整数R，使得$R \times Q \equiv P\pmod{998244353}$且$0 \leq R \lt 998244353$。 找到这样的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$
输出
求以998244353为模的商，表示三个人首次同时在同一个点上的时间的概率，并打印答案。
样例输入1
1 1 3 1
样例输出1
873463809
三个人首次同时在同一个点上的时间的概率为$\frac{1}{8}$。 因为$873463809 \times 8 \equiv 1 \pmod{998244353}$，所以应该打印873463809。
样例输入2
0 0 0 0
样例输出2
1
三个人可能已经在时间0时同时在同一个点上。
样例输入3
0 2 8 9
样例输出3
744570476
样例输入4
47717 21993 74147 76720
样例输出4
844927176