题解：P17762 「奶龙OI」Round 3 - 跑酷大神

_initializer_list_ · 2026-10-24 13:33:21 · 题解

题目传送门

思路

把 a 数组排序，记排好序的数组为 a'，则前 n 个数为“小数”，后 n 个数为“大数”。

如果任意一种排列中每一对都满足一小一大，则交集长度最大为 a'_{n+1} - a'_{n}。

::::info[为什么最大交集长度就是 a'_{n+1}-a'_n？]{open} 排序后前 n 个是小数，后 n 个是大数，大概如下：

\underbrace{a'_1,a'_2,a'_3,\cdots,a'_n}_{\text{小数}},\underbrace{a'_{n+1},a'_{n+2},a'_{n+3},\cdots,a'_{2n}}_{\text{大数}}

我们拿 a' = [1,2,3,4] 来举例：

如果分成 2 个区间为 [1,2],[3,4]，一个区间在左一个区间在右，没有公共部分，交集长度为 0；
如果分成 2 个区间为 [1,3],[2,4]，一大一小配对，中间重叠部分为 [2,3]，长度为 3-2=1。

因此每对一小一大时：

所有对的最小值里，最大的是 a'_n；
所有对的最大值里，最小的是 a'_{n+1}。

一般地：

若有一对两个都是小数，该区间右端点 \le a'_n；剩下 n-1 对里必有一对含大数，其左端点 \ge a'_{n+1}。于是交集左端点 \ge a'_{n+1} > a'_n \ge 右端点，交集为空。
若有一对两个都是大数，对称地交集也为空。
只有“每对一小一大”时交集非空，此时所有左端点恰为全体小数，L=a'_n；所有右端点恰为全体大数，R=a'_{n+1}。交集恰为 [a'_n,a'_{n+1}]，长度 a'_{n+1}-a'_n。

所以交集就是 [a'_n, a'_{n+1}]，长度为 a'_{n+1} - a'_n。

把 n 个跳跃对的位置编号为 1,2,\cdots,n，每对内部顺序确定后，每个位置恰有一个“小位置”和一个“大位置”。

方案数为：

每对里，小的在前还是大的在前：每对 2 种，n 对就是 2^n 种；
把 n 个小数分到 n 个“小位置”上：n! 种；
把 n 个大数分到 n 个“大位置”上：n! 种。

所以方案数是 2^n \times {(n!)}^2。

全部乘起来，取个模，得最终排列数为 \left[(a'_{n+1} - a'_n) \times 2^n \times {(n!)}^2\right] \bmod 998244353，预处理即可。

代码

::::success[AC Code]{open}

// Problem: T810918 「奶龙OI」Round 3 - 跑酷大神
// Contest: Luogu - 【LGR-312-Div.3】洛谷基础赛 #41 & 奶龙 OI Round 3
// URL: https://www.luogu.com.cn/problem/T810918?contestId=345405
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Code by wangxy0311

#include <bits/stdc++.h>
using namespace std;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
template <class T>
T randint(T l, T r) {
    uniform_int_distribution<T> dist(l, r);
    return dist(rnd);
}

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef __int128 i128;
typedef unsigned __int128 u128;
typedef long double ld;

#define rep(x, y, z) for (int x = (y); x <= (z); ++x)
#define per(x, y, z) for (int x = (y); x >= (z); --x)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fileIO(s)               \
  freopen(s ".in", "r", stdin); \
  freopen(s ".out", "w", stdout);
#define endl '\n'
#define all(x) begin(x), end(x)

inline void fast_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

template <typename T>
void chkmax(T &a, T b) { if (b > a) a = b; }
template <typename T>
void chkmin(T &a, T b) { if (b < a) a = b; }

template <int MOD>
struct Modint {
    ll val;
    Modint(ll v = 0) { val = (v % MOD + MOD) % MOD; }
    Modint operator+(const Modint & x) const { return Modint(val + x.val); }
    Modint operator-(const Modint & x) const { return Modint(val - x.val); }
    Modint operator*(const Modint & x) const { return Modint((i128)val * x.val % MOD); }
    Modint operator^(ll b) const { Modint res = 1, a = *this; for (; b; b >>= 1, a *= a) if (b & 1) res *= a; return res; }
    Modint operator^(const Modint & b) const { return *this ^ b.val; }
    Modint operator~() const { return *this ^ MOD - 2; }
    Modint operator/(const Modint & x) const { return *this * ~x; }
    Modint operator-() const { return Modint(-val); }
    Modint & operator+=(const Modint & x) { val = (val + x.val) % MOD; return *this; }
    Modint & operator-=(const Modint & x) { val = (val - x.val + MOD) % MOD; return *this; }
    Modint & operator*=(const Modint & x) { val = (i128)val * x.val % MOD; return *this; }
    Modint & operator^=(ll b) { return *this = *this ^ b; }
    Modint & operator^=(const Modint & b) { return *this = *this ^ b.val; }
    Modint & operator/=(const Modint & x) { return *this = *this / x; }
    Modint & operator++() { return *this += Modint(1); }
    Modint operator++(int) { Modint tmp = *this; ++*this; return tmp; }
    Modint & operator--() { return *this -= Modint(1); }
    Modint operator--(int) { Modint tmp = *this; --*this; return tmp; }
    bool operator==(const Modint & x) const { return val == x.val; }
    bool operator!=(const Modint & x) const { return val != x.val; }
    bool operator<(const Modint & x) const { return val < x.val; }
    bool operator>(const Modint & x) const { return val > x.val; }
    bool operator<=(const Modint & x) const { return val <= x.val; }
    bool operator>=(const Modint & x) const { return val >= x.val; }
    friend Modint operator+(ll v, const Modint & x) { return Modint(v) + x; }
    friend Modint operator-(ll v, const Modint & x) { return Modint(v) - x; }
    friend Modint operator*(ll v, const Modint & x) { return Modint(v) * x; }
    friend Modint operator/(ll v, const Modint & x) { return Modint(v) / x; }
    friend Modint operator^(ll v, const Modint & x) { return Modint(v) ^ x; }
    friend ostream & operator<<(ostream & os, const Modint & x) { return os << x.val; }
    friend istream & operator>>(istream & is, Modint & x) { ll v; is >> v; x = Modint(v); return is; }
};

const int inf = 1e9;
const ll infll = 1e18;
const double eps = 1e-8;
const ld epsll = 1e-12;
const int N = 5e5 + 5;
#define sq(x) ((x) * (x))
const int mod = 998244353;
Modint<mod> pref[N], prep[N];
int a[N];
void init() {
    pref[0] = 1;
    prep[0] = 1;
    rep(i, 1, N / 2) { // 因为数组开大了所以到 N / 2 即可
        pref[i] = pref[i - 1] * i;
        prep[i] = prep[i - 1] * 2;
    }
}
void solve() {
    int n;
    cin >> n;
    rep(i, 1, n * 2) cin >> a[i];
    sort(a + 1, a + n * 2 + 1);
    cout << sq(pref[n]) * prep[n] * (a[n + 1] - a[n]) << endl;
}
int main() {
    fast_io();
    init();
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

:::: 时间复杂度 \mathcal{O}(\sum n \log n)。