No.2013 Can we meet?
Kiri8128
chaemonProblem Statement
Romeo and Juliet are on the $xy$-plane.
Initially, Romeo and Juliet are at the points with coordinates $(x_1,\ y_1)$ and $(x_2,\ y_2)$, respectively.
From here, Romeo and Juliet repeat an action, in which they simultaneously perform the "move to an adjacent point" described below,
until the two meet or the $N$-th action ends.
Here, "the two meet" means that Romeo and Juliet are at the same coordinates after an action.
[Move to an Adjacent Point]
The "move to an adjacent point" from a point $(x,\ y)$ is as follows.- With probability $\frac{A}{2(A+B)}$, instantaneously move to $(x+1,\ y)$
- With probability $\frac{A}{2(A+B)}$, instantaneously move to $(x-1,\ y)$
- With probability $\frac{B}{2(A+B)}$, instantaneously move to $(x,\ y+1)$
- With probability $\frac{B}{2(A+B)}$, instantaneously move to $(x,\ y-1)$
If the two meet after the $i$-th action, they gain a score of $a_i$ and the process ends. If they do not meet after performing $N$ actions, the score gained is $0$. Compute the expected value of the score gained, and output it $\bmod\ 998244353$.
Note that Romeo and Juliet move to adjacent points simultaneously and instantaneously.
All movement directions are determined independently.
Note on output $\bmod\ 998244353$ (click to expand)
It can be proved that the expected value to be found in this problem is a rational number and that, when it is expressed as an irreducible fraction $\frac{p}{q}$, $q$ is not a multiple of $998244353$.Here, an integer $r \ (0 \le r < 998244353)$ satisfying $qr \equiv p \pmod {998244353}$ is uniquely determined, so output this value.
Input
$N$ $x_1\ y_1\ x_2\ y_2$ $A\ B$ $a_1\ a_2\ \cdots\ a_N$
[Constraints]
$1\le N \le 10^5$
$0\le x_1,\ y_1,\ x_2,\ y_2 \le 10^9$
$(x_1,\ y_1) \neq (x_2,\ y_2)$
$1\le A,\ B \le 10^6$
$1 \le a_i \le 10^9 \ (1 \le i \le N)$
All inputs are integers.
Output
Output the expected value of the score $\bmod\ 998244353$.
Print a newline at the end.
Sample
Sample 1
Input
1 0 0 2 0 1 2 5
Output
305019108
If Romeo and Juliet both move to $(1,\ 0)$, the score is $5$; otherwise, the score is $0$.
The probability of the former is $\displaystyle\frac{1}{36}$, so the expected value of the score is $\displaystyle\frac{5}{36}$.
Representing this $\bmod\ 998244353$ and outputting $305019108$ is correct.
Sample 2
Input
2 0 0 2 0 1 1 64 64
Output
7
The two meet after the $1$-st action when Romeo and Juliet are both at coordinates $(1,\ 0)$, and the probability of this is $\displaystyle\frac{1}{16}$.
There are $4$ points where the two can meet after the $2$-nd action, namely $(0,\ 1),\ (0,\ -1),\ (1,\ 0),\ (-1,\ 0)$,
and the probability of meeting at each of them is $\displaystyle\frac{3}{256}$, for a total of $\displaystyle\frac{3}{256} \times 4 =\frac{3}{64}$.
The expected value of the score is $\displaystyle\frac{1}{16} \times 64 + \frac{3}{64} \times 64 = 7$.
Note that if the two meet after the $1$-st action, the process ends without performing the $2$-nd action,
and that they can also move to points with negative $x$- or $y$-coordinates.
Sample 3
Input
1 0 0 1 0 1 1 1000
Output
0
A move in which Romeo and Juliet swap positions may occur, but since moves happen instantaneously, the two do not meet along the way.
Sample 4
Input
5 3 2 6 3 3 2 3 14 15 92 65
Output
91905035
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。