P9330 [JOISC 2023] JOI 国的节日 2 题解

Description

对于以下问题：

给定长度为 $n$ 的序列 $a$、$b$，满足以下条件：

• 在序列 $a$ 与序列 $b$ 中，$1$ 到 $2n$ 的整数各出现恰好一次；
• 对于 $1\leq i\leq n$，$a_i<b_i$；
• 对于 $1\leq i<n$，$a_i<a_{i+1}$。

求：最多能在 $[a_i,b_i]$ 中选出多少个两两不交的区间。

考虑以下算法：

从 $1$ 到 $n$ 枚举 $i$，若 $[a_i,b_i]$ 与所有已经选择的区间都不交，则选择该区间。最后输出选择的区间数。

给定 $n$，求：有多少个满足条件的序列对 $(a,b)$，使得以上算法无法求出正确的结果。答案对 $p$ 取模。

$1\leq n\leq 2\times 10^4$，$P$ 是质数。

Solution

首先正确的策略一定是按照右端点从小到大贪心。考虑用总方案数减去最终结果正确的方案数。

不妨将第二种策略选的线段看成红色，第一种看成蓝色，两种同时选的看成紫色，都没选的看成黑色，那么将线段按照右端点排序后一定是红蓝交替或者紫色排列在一起。如图：

然后考虑红线段的性质：

1. 红线段不交。
2. 前一个红线段的右端点到下一个红线段的左端点之间不存在完整的线段。

蓝线段：

1. 蓝线段不交。
2. 前一个蓝线段的右端点到下一个蓝线段的左端点之间不存在某个线段的左端点。

那么就可以 dp 了。

然后考虑从前往后每次插入一对红蓝或者紫线段，设 $f_{i,j,0/1}$ 表示已经插入了 $i$ 个线段，有 $j$ 个左端点尚未匹配，且最后是红蓝/紫线段的方案数。

转移时枚举插入的黑色线段数量即可。时间复杂度：$O(n^3)$，过不了。

---

注意到上面那个做法枚举黑色线段数量这部分是无法省略的，所以考虑优化状态数量。

由于这题对左端点的限制强于右端点，所以考虑倒着插入线段，同时为左端点找其匹配的右端点。这样会发现只要确定了左端点的位置之后，右端点就随便选了。

具体地，设 $f_{i,0/1}$ 表示目前倒着插入了 $i$ 个线段，最后插入的是红蓝/紫线段，且目前已经为大于最前面的红/紫线段的右端点 的左端点找到匹配的右端点的方案数。

然后考虑转移。这里只讨论 $0\to 0$ 的转移。有两种情况，需要分类讨论：

上图是第一种情况。先枚举加入的黑色线段的左端点个数 $j$，容易发现这 $j$ 个左端点只能放在上图中的前三个区间里，由于此时并没有给上一步最后添加到两个线段分配左端点，所以可以先固定 $j$ 个加入的左端点，然后用上一步最后线段的左端点将其分成三部分，方案数为 $\frac{(j+1)(j+2)}{2}$。

然后是为这 $j$ 个左端点找到匹配的右端点。注意到右端点可以插在最后一个区间内的任何位置，而这个区间有 $2i-2$ 个段，方案数即为 $(2i-2)^{\overline{j}}$。于是这种情况的贡献为 $f_{i,0}\times\frac{(j+1)(j+2)}{2}\times(2i-2)^{\overline{j}}$。

这是第二种情况，和第一种情况贡献是一样的。所以转移式为 $f_{i+j+2,0}\leftarrow f_{i,0}\times(j+1)(j+2)\times(2i-2)^{\overline{j}}$。

其余三种转移是类似的。

求答案时还需要枚举最后加了多少个黑色线段，贡献也是类似的。

时间复杂度：$O(n^2)$，卡常后可过。

Code

#include <bits/stdc++.h>

// #define int int64_t

using i64 = int64_t;

const int kMaxN = 2e4 + 5;

int n, mod;
int fac[kMaxN * 2], ifac[kMaxN * 2], f[kMaxN][2];

struct Barrett {
  int64_t m, p;
  void init(int64_t mod) {
    m = ((__int128_t)1 << 64) / mod;
    p = mod;
  }
  Barrett(int64_t mod = 2) { init(mod); }
  inline int64_t operator()(int64_t x) {
    x -= (((__int128_t)x * m) >> 64) * p;
    return x >= p ? x - p : x;
  }
} Reduce;

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

inline int add(int x, int y) { return (x + y >= mod ? x + y - mod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + mod); }
inline int mul(int x, int y) { return Reduce(1ll * x * y); }
inline void inc(int &x, int y) { (x += y) >= mod ? x -= mod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += mod : x; }
inline void multi(int &x, int y) { x = Reduce(1ll * x * y); }

inline int getfac(int l, int r) {
  return l <= 0 ? 0 : 1ll * fac[r] * ifac[l - 1] % mod;
}

inline int up(int x, int k) {
  return getfac(x, x + k - 1);
}

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

void dickdreamer() {
  std::cin >> n >> mod;
  Reduce.init(mod);
  prework(2 * n);
  f[1][1] = f[2][0] = 1;
  for (int i = 1; i < n; ++i) {
    for (int o1 = 0; o1 <= 1; ++o1) {
      if (!f[i][o1]) continue;
      for (int o2 = 0; o2 <= 1; ++o2) {
        int tmp = 1ll * f[i][o1] * ifac[2 * i - 2 + o1 - 1] % mod;
        for (int j = 0; j <= n - i - 2 + o2; ++j) {
          int coef = tmp;
          multi(coef, fac[2 * i - 2 + o1 + j - 1]);
          if (!o1) multi(coef, j + 1);
          if (!o2) multi(coef, j + !o1 + !o2);
          inc(f[i + j + 2 - o2][o2], coef);
        }
      }
    }
  }
  int ans = 1;
  for (int i = 1; i <= 2 * n; i += 2) ans = 1ll * i * ans % mod;
  for (int i = 1; i <= n; ++i) {
    int j = n - i;
    dec(ans, 1ll * (j + 1) * up(2 * i - 2, j) % mod * f[i][0] % mod);
    dec(ans, 1ll * up(2 * i - 1, j) * f[i][1] % mod);
  }
  std::cout << ans << '\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;
}