問題一覧 > 通常問題

No.1864 Shortest Paths Counting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : ChipppppChippppp / テスター : ぷらぷら shiomusubi496shiomusubi496
4 ProblemId : 7343 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-20 11:14:46

問題文

二次元平面上に異なる $N$ 個の点があり,$1$ から $N$ までの番号がつけられています.点 $i$ の座標は $(X_i, Y_i)$です.

$(x_0, y_0)$ と $(x_1, y_1)$ の距離は $\max(|x_0 - x_1|, |y_0 - y_1|)$ で定義されます.

このとき,いくつかの点を経由して点 $1$ から点 $N$ へ移動する経路であって,移動距離の合計が最小となるものの個数を求めてください.
より正確には,$p_1 = 1$,$p_k = N$,$1 \leq p_i \leq N$ $(1 \leq i \leq k)$ 及び $p_i \neq p_{i+1}$ $(1 \leq i \leq k - 1)$ (22:35 追記) を満たす長さ $k$ の正整数列 $p$ であって,$\displaystyle\sum_{i = 1}^{k - 1} \max(|X_{p_{i + 1}} - X_{p_i}|, |Y_{p_{i + 1}} - Y_{p_i}|)$ が最小となるものの個数を求めてください.
なお、答えは非常に大きくなることがあるので、 $998244353$ で割った余りを出力してください.

入力

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

  • $2 \le N \le 2 \times 10 ^ 5$
  • $-10 ^ 9 \le X_i, Y_i \le 10 ^ 9$ $(1 \le i \le N)$
  • $(X_i, Y_i) \neq (X_j, Y_j)$ $(i \neq j)$
  • 入力は全て整数
  • 出力

    距離の総和が最小となる移動方法の個数を $998244353$ で割った余りを出力してください.
    また,最後に改行を出力してください.

    サンプル

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

    以下の $2$ つの経路が条件を満たします.

    • 点 $1$ $\to$ 点 $3$
    • 点 $1$ $\to$ 点 $2$ $\to$ 点 $3$

    例えば $2$ つ目の経路では,距離の合計は $\max(|0-0|, |0-1|) + \max(|0-1|, |2-1|) = 1 + 1 = 2$ となります.

    サンプル2
    入力
    5
    0 6
    1 5
    3 2
    5 5
    3 0
    出力
    4

    以下の $4$ つの経路が条件を満たします。

    • 点 $1$ → 点 $5$
    • 点 $1$ → 点 $2$ → 点 $5$
    • 点 $1$ → 点 $3$ → 点 $5$
    • 点 $1$ → 点 $2$ → 点 $3$ → 点 $5$
    サンプル3
    入力
    10
    -8 1
    3 -5
    -4 8
    5 -4
    -1 -6
    6 0
    -1 -4
    2 -9
    -6 7
    10 -9
    出力
    14

    サンプル4
    入力
    14
    0 0
    7 -7
    11 -3
    9 -1
    7 1
    7 -5
    10 -2
    8 0
    4 4
    5 1
    5 3
    7 -3
    6 2
    12 -4
    
    出力
    334

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