P16433 [APIO 2026 中国赛区] 上升

PTqwq · 2026-05-12 12:13:01 · 题解

分享一个考场做法，但是因为一些原因场上只拿到了模数是质数的 90 分。

第一次容斥

首先我们要求的是 \displaystyle \prod_{i \in S(q)}w_i，但是如果我们直接精确的确定 S(q)，计数起来其实并不是很容易，所以我们先做一个变形，将贡献形式转化为：

\sum_{T \subseteq S(q)}\prod_{i \in T}(w_i - 1)

这样我们只需要钦定 T，限制 \forall i \in T, q_i < q_{i + 1} 即可。

分析限制

首先令 p_0 = -1, p_{n + 1} = n + 1。

这样整个排列 p 中空缺的位置形成若干个区间 [l_1, r_1], [l_2, r_2], \dots, [l_q, r_q]。

我们需要对 \{l_i - 1, r_i\} = T \cap \{l_i - 1, l_i, l_i + 1, \dots, r_i\} 是否成立进行分类讨论：

成立：那么需要满足 \boldsymbol{p_{l_i - 1}} < p_{l_i} < p_{l_i + 1} < \dots < p_{r_i} < \boldsymbol{p_{r_i + 1}}。
不成立：此时 [l_i, r_i] 被分成了若干个区间 [x_1, y_1], [x_2, y_2], \dots, [x_k, y_k](k \geq 2)，其中 [x_1, y_1] 和 [x_k, y_k] 可以为空并且分别要和 l_i - 1, r_i + 1 形成同一个上升段，而 [x_2, y_2], [x_3, y_3], \dots, [x_{k - 1}, y_{k - 1}] 自己形成一个上升段。

设计一个 DP！

设 f_{i, j} 表示考虑了 q_1, q_2, \dots, q_i，当前 \leq \max\{p_0, p_1, \dots, p_i\} 的数还有 j 个没有放到排列里面（其实这个如果在考虑区间 [l_i, r_i]，那就相当于 \leq p_{l_i - 1}）

考虑 f_{l_i - 1, *} \to f_{r_i, *}，对于 \{l_i - 1, r_i\} = T \cap \{l_i - 1, l_i, l_i + 1, \dots, r_i\} 成立的情形，我们只需要从 [p_{l_i - 1} + 1, p_{r_i + 1} - 1] 中选择 r_i - l_i + 1 个数并将剩下的数扔到第二维里面即可，系数仅为一个组合数。

而对于条件不成立的情形，[x_k, y_k] 的限制仍可以用类似的方法处理，对于 [x_2, y_2], [x_3, y_3], \dots, [x_{k - 1}, y_{k - 1}]，可以延迟钦定，先乘上 \dfrac{1}{(y_i - x_i + 1)!} 的系数，到最后 f_{n, y} 的时候再乘上 y! 就形成了一个多重组合数的系数。也可以理解成先让 [x_i, y_i] 无序，然后除以 (y_i - x_i + 1)! 进行限制。

处理 [x_1, y_1] 的限制

先考虑让 [x_1, y_1] 无序，容斥其中有 m 个位置 > p_{l_i - 1}，令 y 为当前 < p_{l_i - 1} 的还没有填的数的个数，那么系数就是：

(-1)^m\dbinom{y_1 - x_1 + 1}{m}\dbinom{y}{m}m!\dfrac{1}{(y_1 - x_1 + 1)!}

化简得到：

(-1)^m\dbinom{y}{m}\dfrac{1}{(y_1 - x_1 + 1 - m)!}

这样可以做到 O(n^3) 通过 B 性质。

处理 \dfrac{1}{k!} 的逆元问题

此时你发现当前乘上的所有的 \dfrac{1}{k!} 的 \displaystyle \sum k 其实根据一些组合意义是等于 p_0, p_1, \dots, p_i 中 0 的个数减去已经填了的 \leq p_{*} 的数的个数，于是可以直接用组合数来代替阶乘的逆元。

于是这个题就做完了，复杂度 O(n^3)，代码：

#include "ascend.h"
#include <bits/stdc++.h>

using namespace std;

long long infoC[580][580];
long long f[580][580], g[580][580], h[580][580], a[580], b[580], info[580], fac[580], mod;
int pre_good[580];

long long binomC(long long n, long long m) {
  if (n < 0 || m < 0 || n < m) {
    return 0;
  }
  return infoC[n][m];
}

int get_remainIdx(int x, int y, int z) {
  return (pre_good[x] - (z - y));
}

long long dp[1 << 20][20], dp2[580][580];

int ascend(int c, int n, int m, vector<int> p, vector<int> w) {
  mod = 1ll * m;

  for (int i = 0; i <= 520; ++ i) {
    for (int j = 0; j <= 520; ++ j) infoC[i][j] = 0;
  }
  infoC[0][0] = 1;
  for (int i = 1; i <= 520; ++ i) {
    infoC[i][0] = 1;
    for (int j = 1; j <= i; ++ j) infoC[i][j] = (infoC[i - 1][j] + infoC[i - 1][j - 1]) % mod;
  }

  fac[0] = 1;
  for (long long i = 1; i <= 510; ++ i) {
    fac[i] = fac[i - 1] * i % mod;
  }

  a[1] = 1;
  a[n + 2] = n + 2;
  for (int i = 1; i <= n; ++ i) {
    int x = p[i - 1];
    if (x != 0) {
      a[i + 1] = x + 1;
    } else {
      a[i + 1] = 0;
    }
  }
  b[1] = 0;
  b[n + 1] = 0;
  for (int i = 2; i <= n; ++ i) {
    b[i] = w[i - 2];
    b[i] = (b[i] + mod - 1) % mod;
  }

  pre_good[0] = 0;
  for (int i = 1; i <= n + 3; ++ i) {
    pre_good[i] = pre_good[i - 1];
    if (a[i] == 0) pre_good[i] ++;
  }

  for (int i = 0; i <= n + 3; ++ i) {
    for (int j = 0; j <= n + 3; ++ j) {
      f[i][j] = 0;
      g[i][j] = 0;
      h[i][j] = 0;
    }
  }

  f[0][0] = 1;
  int pos = 0, now_empty_num = 0;
  for (int i = 2; i <= n + 1; ++ i) {
    if (a[i] == 0 && a[i - 1] != 0) {
      int cur_add = a[i - 1] - a[pos + 1] + 1;
      int cur_len = (i - 1) - pos;
      cur_add -= cur_len;

      now_empty_num += cur_add;

      int j = i;
      while (a[j + 1] == 0 && j + 1 <= n + 2) ++ j;
      for (int x = cur_add; x <= n + 3; ++ x) g[i - 1][x] = f[pos][x - cur_add];
      for (int x = 0; x < cur_add; ++ x) g[i - 1][x] = 0;

      if (a[j + 1] - a[i - 1] - 1 >= j - i + 1) {
        long long cur_coef = binomC(a[j + 1] - a[i - 1] - 1, j - i + 1);
        for (int x = i - 1; x <= j; ++ x) cur_coef = cur_coef * b[x] % mod;
        int rem = (a[j + 1] - a[i - 1] - 1) - (j - i + 1);
        for (int x = 0; x + rem <= n + 3; ++ x) {
          if (g[i - 1][x] != 0) {
            f[j][x + rem] = (f[j][x + rem] + g[i - 1][x] * cur_coef) % mod;
          }
        }
      }
      for (int x = i - 1; x <= j; ++ x) {
        for (int y = x - (i - 1); y <= n + 3; ++ y) {
          long long cur_coef = binomC(y, x - (i - 1));
          if ((x - (i - 1)) % 2 == 1) cur_coef = (mod - cur_coef % mod) % mod;
          h[x][y - (x - (i - 1))] = (h[x][y - (x - (i - 1))] + g[i - 1][y] * cur_coef) % mod;
        }
      }
      for (int x = i - 1; x <= j; ++ x) {
        for (int y = 0; y <= n + 3; ++ y) {
          for (int z = max(i, z); z <= j; ++ z) {
            if (h[x][y] == 0) continue;
            g[z][y] = (g[z][y] + h[x][y] * binomC(get_remainIdx(z, y, now_empty_num), z - x)) % mod;
          }
        }
      }
      for (int x = i; x <= j; ++ x) {
        long long cur_coef = 1;
        for (int y = i - 1; y < x; ++ y) cur_coef = cur_coef * b[y] % mod;
        for (int y = 0; y <= n + 3; ++ y) g[x][y] = g[x][y] * cur_coef % mod;
      }
      for (int x = i - 1; x <= j; ++ x) {
        long long now_prod = 1;
        for (int y = x + 1; y <= j; ++ y) {
          if (y - 1 >= x + 1) {
            now_prod = now_prod * b[y - 1] % mod;
          }
          int cnt_add = y - x;
          for (int z = 0; z <= n + 3; ++ z) {
            if (g[x][z] == 0) continue;
            g[y][z] = (g[y][z] + g[x][z] * binomC(get_remainIdx(y, z, now_empty_num), cnt_add) % mod * now_prod) % mod;
          }
        }
      }
      int now_add = a[j + 1] - a[i - 1] - 1;
      now_empty_num += now_add;
      for (int x = i - 1; x <= j; ++ x) {
        for (int y = n + 3; y >= now_add; -- y) {
          g[x][y] = g[x][y - now_add];
        }
        for (int y = 0; y < now_add; ++ y) g[x][y] = 0;
      }
      for (int x = i - 1; x <= j; ++ x) {
        long long now_prod = 1;
        for (int y = x + 1; y <= j; ++ y) {
          now_prod = now_prod * b[y] % mod;
        }
        int cnt_now = j - x;
        for (int y = cnt_now; y <= n + 3; ++ y) {
          f[j][y - cnt_now] = (f[j][y - cnt_now] + g[x][y] * binomC(y, cnt_now) % mod * now_prod) % mod;
        }
      }

      pos = j;
    }
  }

  int now_add = a[n + 2] - a[pos + 1] + 1;
  int now_len = n + 2 - pos;
  now_add -= now_len;

  long long ans = 0;
  for (int i = now_add; i <= n + 3; ++ i) {
    ans = (ans + f[pos][i - now_add]) % mod;
  }

  for (int i = 1; i <= n + 1; ++ i) {
    if (a[i] != 0 && a[i + 1] != 0) {
      ans = ans * (b[i] + 1ll) % mod;
    }
  }

  ans = (ans % mod + mod) % mod;
  ans %= mod;
  return ans;
}