問題一覧 > 通常問題

No.2013 Can we meet?

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : Kiri8128Kiri8128 / テスター : chaemonchaemon
0 ProblemId : 8027 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-01 21:13:41

問題文

$xy$ 平面上にロミオ君とジュリエットさんがいます。 最初ロミオ君とジュリエットさんはそれぞれ座標が $(x_1,\ y_1)$ および $(x_2,\ y_2)$ で表される点にいます。 ここからロミオ君とジュリエットさんは後述の「隣接点への移動」を同時に行うという 行動 を、 ふたりが出会うかまたは $N$ 回目の行動が終わるまで 繰り返します。 ただし「ふたりが出会う」とは、行動のあとにロミオ君とジュリエットさんが同じ座標に存在することを言います。

【隣接点への移動】
点 $(x,\ y)$ にいるときの「隣接点への移動」は次のとおりです。
  • $\frac{A}{2(A+B)}$ の確率で $(x+1,\ y)$ に瞬間的に移動する
  • $\frac{A}{2(A+B)}$ の確率で $(x-1,\ y)$ に瞬間的に移動する
  • $\frac{B}{2(A+B)}$ の確率で $(x,\ y+1)$ に瞬間的に移動する
  • $\frac{B}{2(A+B)}$ の確率で $(x,\ y-1)$ に瞬間的に移動する

$i$ 回目の行動後にふたりが出会った場合は、スコア $a_i$ を獲得して終了します。 行動を $N$ 回行っても出会わなかった場合は獲得するスコアは $0$ です。 獲得するスコアの期待値を計算し、 $\bmod\ 998244353$ で出力してください。

隣接点への移動はロミオ君とジュリエットさんが同時に、かつ瞬間的に行うことに注意してください。
なお移動方向の決定はすべて独立に行われます。

  • $\bmod\ 998244353$ での出力についての注記（クリックすると展開されます）
    •
    この問題において求める期待値は有理数であり、既約分数 $\frac{p}{q}$ で表したときに $q$ は $998244353$ の倍数でないことが証明できます。
    ここで、 $qr \equiv p \pmod {998244353}$ を満たす整数 $r \ (0 \le r < 998244353)$ が一意に定まるので、この値を出力してください。

    入力

    $N$
$x_1\ y_1\ x_2\ y_2$
$A\ B$
$a_1\ a_2\ \cdots\ a_N$

    【制約】
    $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)$
    入力はすべて整数

    出力

    スコアの期待値を $\bmod\ 998244353$ で出力してください。
    最後に改行してください。

    サンプル

    サンプル1
    入力
    1
0 0 2 0
1 2
5
    出力
    305019108

    ロミオ君とジュリエットさんがともに $(1,\ 0)$ に移動した場合のスコアは $5$ 、それ以外の場合のスコアは $0$ です。 前者が起こる確率は $\displaystyle\frac{1}{36}$ なので、スコアの期待値は $\displaystyle\frac{5}{36}$ です。
    これを $\bmod\ 998244353$ で表した $305019108$ を出力すると正解になります。

    サンプル2
    入力
    2
0 0 2 0
1 1
64 64
    出力
    7

    $1$ 回目の行動後にふたりが出会うのは、ロミオ君とジュリエットさんがともに座標 $(1,\ 0)$ にいる場合で、その確率は $\displaystyle\frac{1}{16}$ です。
    $2$ 回目の行動後にふたりが出会うことができる座標は $(0,\ 1),\ (0,\ -1),\ (1,\ 0),\ (-1,\ 0)$ の $4$ 点あり、 それぞれで出会う確率は $\displaystyle\frac{3}{256}$ ずつ、合計で $\displaystyle\frac{3}{256} \times 4 =\frac{3}{64}$ です。
    スコアの期待値は $\displaystyle\frac{1}{16} \times 64 + \frac{3}{64} \times 64 = 7$ です。
    $1$ 回目の行動後にふたりが出会った場合は $2$ 回目の行動をせず終了すること、 $x$ 座標や $y$ 座標が負の点にも移動できることなどに注意してください。

    サンプル3
    入力
    1
0 0 1 0
1 1
1000
    出力
    0

    ロミオ君とジュリエットさんの位置が互いに入れ替わるような移動が起こる可能性がありますが、 移動は瞬間的に起こるので途中でふたりが出会うことはありません。

    サンプル4
    入力
    5
3 2 6 3
3 2
3 14 15 92 65
    出力
    91905035

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。