問題一覧 > 通常問題

No.2615 ペアの作り方

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 147
作問者 : startcpp / テスター : 👑 p-adic
4 ProblemId : 7660 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-21 21:47:52

問題文

長さ NN の整数列 (X1,⋯ ,XN)(X_1, \cdots, X_N), (Y1,⋯ ,YN)(Y_1, \cdots, Y_N) があります。
(1,2,⋯ ,N)(1, 2, \cdots , N) の並べ替え P=(P1,⋯ ,PN)P = (P_1, \cdots, P_N) について、 f(P)=∑i=1Nmin⁡(Xi,YPi)f(P) = \sum_{i=1}^{N} \min(X_i, Y_{P_i}) とするとき、
f(P)f(P) が最小となる PP は何通りあるでしょうか？
答えを 998244353998244353 で割った余りを求めてください。

入力

NN
X1X_1 ⋯\cdots XNX_N
Y1Y_1 ⋯\cdots YNY_N
  • 入力は整数
  • 1≤N≤1051 \le N \le 10^5
  • 1≤Xi≤1091 \le X_i \le 10^9
  • 1≤Yi≤1091 \le Y_i \le 10^9
  • 2N2N 個の整数 X1,⋯ ,XN,Y1,⋯ ,YNX_1, \cdots, X_N, Y_1, \cdots, Y_N は互いに異なる

出力

答えを 998244353998244353 で割った余りを 11 行に出力してください。
最後に改行してください。

サンプル

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

P=(2,3,1)P = (2, 3, 1) または P=(3,2,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

最小になる PP は 1440014400 通りあります。

サンプル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

条件を満たす PP は 1463132160014631321600 通りあります。
よって、これを 998244353998244353 で割った余りである 655900658655900658 を出力します。

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