問題一覧 > 通常問題

No.1864 Shortest Paths Counting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : 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もしくは右上の雲マークをクリックしてアカウントを作成してください。