QOJ #10331. Shuffle and Max Bracket Score 题解

Description

对于一个长度为 $2n$ 的序列 $b_1,b_2,\ldots,b_{2n}$，定义 $t_i=1$ 表示第 $i$ 个位置是左括号，否则为右括号。序列的权值为满足这个括号序列合法的条件下，$\sum b_it_i$ 的最大值。

现在给一个序列 $a_1,a_2,\ldots,a_{2n}$，问将其随机打乱的期望权值。

对 $998244353$ 取模。

$n\leq 10^5$。

Solution

先考虑怎么求一个给定序列的权值。

设 $p_i$ 表示第 $i$ 个左括号的位置，那么如果所有 $p_i$ 都不超过 $2i-1$ 则这个序列一定合法，容易证明这是充要条件。

现在就可以得到一个贪心做法：从前往后枚举序列的每一个数，每次将 $a_i$ 加到大根堆里，如果 $i$ 是奇数则弹出大根堆堆顶元素，弹出的就是选择左括号的位置。

---

考虑怎么求期望。

上面那个东西还是过于复杂，不适合计数。

套路性地，先对序列进行离散化，对于每个 $a_i$，将 $\geq a_i$ 的看成 $1$，$<a_i$ 的看成 $0$，就转化为了 $01$ 问题。

现在变为对于每个 $s$，求有 $s$ 个 $1$，$2n-s$ 个 $0$ 的期望权值，设其为 $f(s)$。

容易发现最后被选到的 $1$ 一定是一段前缀，所以可以用 Hall 定理的思想，没有选到的 $1$ 的个数为：所有后缀中 $a_i$ 之和减需要进行匹配的位置的个数的最大值。写成式子：

$$\begin{aligned} ans&=s-\max_{k}{\left\{s-\sum_{i=1}^{k}{a_i}-\left\lfloor\frac{2n-k}{2}\right\rfloor\right\}}\\ &=\min_{k}{\left\{\sum_{i=1}^{k}{a_i}+\left\lfloor\frac{2n-k}{2}\right\rfloor\right\}}\\ &=n+\min_{k}{\left\{\sum_{i=1}^{k}{a_i}+\left\lfloor\frac{-k}{2}\right\rfloor\right\}}\\ &=n+\min_{k}{\left\{\left\lfloor\frac{\sum_{i=1}^{k}{(2a_i-1)}}{2}\right\rfloor\right\}} \end{aligned}$$

上面转化为了求 $2a_i-1$ 的最小前缀和，而这个东西的值域是 $\{1,-1\}$，就是括号匹配的那个东西！

设 $g(s,t)$ 表示有 $s$ 个 $1$，答案不小于 $t$ 的方案数，推一下式子容易得到 $\displaystyle g(s,t)=\binom{2n}{s}-\binom{2n}{2t-s-1}$。

所以 $\displaystyle f(s)=\sum_{t=0}^{\min\{s,n\}}{\left[\binom{2n}{s}-\binom{2n}{2t-s-1}\right]}$，维护一下奇偶的组合数前缀和即可。

时间复杂度：$O(n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 2e5 + 5, kMod = 998244353;

int n;
int a[kMaxN], p[kMaxN], fac[kMaxN], ifac[kMaxN], sum[kMaxN], f[kMaxN];

int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

int C(int m, int n) {
  if (m < n || m < 0 || n < 0) return 0;
  return 1ll * fac[m] * ifac[n] % kMod * ifac[m - n] % kMod;
}

void prework() {
  fac[0] = 1;
  for (int i = 1; i <= 2 * n; ++i) fac[i] = 1ll * i * fac[i - 1] % kMod;
  ifac[2 * n] = qpow(fac[2 * n]);
  for (int i = 2 * n; i; --i) ifac[i - 1] = 1ll * i * ifac[i] % kMod;
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= 2 * n; ++i) std::cin >> a[i];
  std::sort(a + 1, a + 1 + 2 * n);
  prework();
  int ans = 0;
  for (int i = 0; i <= 2 * n; ++i)
    sum[i] = add(C(2 * n, i), i <= 1 ? 0 : sum[i - 2]);
  for (int i = 1; i <= 2 * n; ++i) {
    int lim = std::min(i, n);
    f[i] = 1ll * lim * C(2 * n, i) % kMod;
    if (2 * lim - i - 1 >= 0) dec(f[i], sum[2 * lim - i - 1]);
  }
  for (int i = 1; i <= 2 * n; ++i)
    inc(ans, 1ll * (a[i] - a[i - 1]) * f[2 * n - i + 1] % kMod * fac[i - 1] % kMod * fac[2 * n - i + 1] % kMod);
  std::cout << 1ll * ans * ifac[2 * n] % kMod << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}