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

· · 题解

题目传送门

题意

就是把 a_i 进行重排，得到 b_i。每个 b_i 的贡献就是所有 [b_1,b_2],[b_3,b_4]\dots [b_{2n-1},b_{2n}] 区间的交区间的长度。

求所有排列的贡献和。

分析

我们先把 a_i 排序。

可以发现，只有每个区间的两个端点分别在不同的半段时，才有可能有贡献，而这个贡献必须是 a_{n+1}-a_n。

那么有多少个这样的贡献呢？前半段和后半段和可以任意排序，那么就有 (n!)^2 个贡献。然而，区间的两端也可以换顺序，就是 2^n 种情况。

所以答案就是：

(a_{n+ 1}-a_n)\times (n!)^2\times 2^n

代码

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MOD = 998244353 ; 
int n , a[400005] ;
ll fac[400005] , inv[400005] ;
ll ksm(ll a , int b = MOD - 2)
{
  ll mul = 1 ;
  while(b)
  {
    if(b & 1) mul = mul * a % MOD ;
    a = a * a % MOD ;
    b >>= 1 ;
  }
  return mul ;
}
void init()
{
  fac[0] = 1 ;
  for( int i = 1 ; i <= 400000 ; i++ ) fac[i] = fac[i - 1] * i % MOD ;
}
void solve()
{
  cin >> n ;
  for( int i = 1 ; i <= 2 * n ; i++ ) cin >> a[i] ;
  sort(a + 1 , a + 2 * n + 1) ;
  ll as = (a[n + 1] - a[n]) % MOD ;
  as = as * fac[n] % MOD * fac[n] % MOD ;
  as = as * ksm(2 , n) % MOD ;
  cout << as << "\n" ;
}
int main()
{
  ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int oT_To = 1 ;
  cin >> oT_To ;
  init() ;
  while(oT_To--) solve() ;
  return 0 ;
}