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

· · 题解

题意

给定一个数列 a_1,a_2,\ldots,a_{2n}，描述了 n 对区间 [a_1, a_2),[a_3,a_4),\ldots,[a_{2n-1}, a_{2n})。这个数列的价值即为这些区间的交集的长度。

将 a 数列进行全排列，得到 (2n)! 个不同的数列，求它们的价值总和。对 998244353 取模。

思路

我们发现考虑所有的数列并逐个求交集是困难的。因此转化题意。我们考察所有数轴上的点，对于每个点 i，求有多少种排列使得 i 在最后的交集中。由于区间端点全为整数，显然我们只需要考虑整点即可。

对于整点 i 和数列 a，i 出现在最后的交集中，等价于所有的区间 [l,r) 都满足 l\le i 且 r>i。这样的区间总共有 n 个。也就是说，我们要在 2n 个数中找出 n 个 \le i 的和 n 个 >i 的数。显然，i 最小是将 a 排升序后的 a_n。并且不难进一步发现，有且仅有 [a_n, a_{n+1}) 中的整点满足条件。于是仅有数轴上落在 [a_{n+1}-a_n) 的整点，有可能出现在最终的交集中产生贡献。

现在考虑计数。这 n 个区间没有限制顺序。换言之，n 个左端点和 n 个右端点自由排列。所以有 (n!)^2 种方案。进一步我们发现，对于已经排好的 n 个区间，每个区间交换左右端点对答案没有影响。于是我们可以在 n 个区间中任选 j 个，各自交换左右端点。所以又有 \sum_{j=0}^n\binom{n}{j} = 2^n 种方案。

综上，答案是 (a_{n+1}-a_n)\cdot (n!)^2\cdot 2^n。

时间复杂度为 \mathcal{O}(\sum n\log n)。瓶颈在于排序。

代码

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define MIKU 0
using namespace std;

const int mod = 998244353;
int T;
int n, a[400005], fac[200005];

int qpow(int a, int n, int res=1) {
    for(; n; n>>=1) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for(int i=1; i<=200005; i++) fac[i] = fac[i-1] * i % mod;
}

void work() {
    cin>>n;
    for(int i=1; i<=2*n; i++) cin>>a[i];
    sort(a+1, a+2*n+1);
    int d = a[n+1] - a[n];
    int ans = d * fac[n] % mod * fac[n] % mod * qpow(2, n) % mod;
    cout<<ans<<'\n';
}

signed main() {
    fastio;
    cin>>T;
    init();
    while(T--) work();
    return MIKU;
}