問題一覧 > 通常問題

No.2615 Ways to Make Pairs

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 164
作問者 : startcpp / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 7660 / 自分の提出
問題文最終更新日: 2023-12-21 21:47:52
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 416 (順位表) の他の問題:

Problem Statement

You are given integer sequences $(X_1, \cdots, X_N)$, $(Y_1, \cdots, Y_N)$ of length $N$.
For a permutation $P = (P_1, \cdots, P_N)$ of $(1, 2, \cdots , N)$, let $f(P) = \sum_{i=1}^{N} \min(X_i, Y_{P_i})$.
How many permutations $P$ minimize $f(P)$?
Find the answer modulo $998244353$.

Input

$N$
$X_1$ $\cdots$ $X_N$
$Y_1$ $\cdots$ $Y_N$
  • All inputs are integers.
  • $1 \le N \le 10^5$
  • $1 \le X_i \le 10^9$
  • $1 \le Y_i \le 10^9$
  • The $2N$ integers $X_1, \cdots, X_N, Y_1, \cdots, Y_N$ are pairwise distinct.

Output

Print the answer modulo $998244353$ on $1$ line.
End the output with a newline.

Sample

Sample 1
Input
3
1 3 5
2 4 6
Output
2

The minimum is attained when $P = (2, 3, 1)$ or $P = (3, 2, 1)$.

Sample 2
Input
10
58 1001 869120 57 97 425 91 224 8679 55663
1999 19980412 1998 2333 48 300 239 2005 111 399
Output
14400

There are $14400$ permutations $P$ that attain the minimum.

Sample 3
Input
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
Output
655900658

There are $14631321600$ permutations $P$ that satisfy the condition.
Therefore, print $655900658$, which is this number modulo $998244353$.

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