No.2615 ペアの作り方
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 144
作問者 :
startcpp
/ テスター :
👑 
p-adic
タグ : / 解いたユーザー数 144
作問者 :
startcpp
/ テスター :
👑 p-adic
問題文最終更新日: 2023-12-21 21:47:52
問題文
長さ $N$ の整数列 $(X_1, \cdots, X_N)$, $(Y_1, \cdots, Y_N)$ があります。$(1, 2, \cdots , N)$ の並べ替え $P = (P_1, \cdots, P_N)$ について、 $f(P) = \sum_{i=1}^{N} \min(X_i, Y_{P_i})$ とするとき、
$f(P)$ が最小となる $P$ は何通りあるでしょうか？
答えを $998244353$ で割った余りを求めてください。
入力
$N$ $X_1$ $\cdots$ $X_N$ $Y_1$ $\cdots$ $Y_N$
- 入力は整数
- $1 \le N \le 10^5$
- $1 \le X_i \le 10^9$
- $1 \le Y_i \le 10^9$
- $2N$ 個の整数 $X_1, \cdots, X_N, Y_1, \cdots, Y_N$ は互いに異なる
出力
答えを $998244353$ で割った余りを $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 1 3 5 2 4 6
出力
2
$P = (2, 3, 1)$ または $P = (3, 2, 1)$ のとき、最小になります。
サンプル2
入力
10 58 1001 869120 57 97 425 91 224 8679 55663 1999 19980412 1998 2333 48 300 239 2005 111 399
出力
14400
最小になる $P$ は $14400$ 通りあります。
サンプル3
入力
17 1 3 4 7 10 11 14 15 16 20 21 23 26 27 28 33 34 2 5 6 8 9 12 13 17 18 19 22 24 25 29 30 31 32
出力
655900658
条件を満たす $P$ は $14631321600$ 通りあります。
よって、これを $998244353$ で割った余りである $655900658$ を出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。