P16433

Whitely · 2026-05-10 16:41:37 · 题解

::::info[闲话] 做了半场，调试出大量错误，最后和正解相差一个系数。

很多问题手推时并不能及时发现，仍需靠平时多加练习。

本题再次警示我处理细节能力的重要性，平时一定不能忽略代码实现或再依靠 AI 调试。 ::::

下面定义 关键位 表示初始有值的位，设这些位的下标分别为 q_{1\dots z}，值分别为 v_{1\dots z}，定义 段 i 表示 [q_i,q_{i+1}] 下标段，所有数组均为 1-index。

思考处理顺序，贡献和真实位置相关，将值按顺序插入不可取，考虑从前到后做。

而确定前缀中每一位的具体值显然做不到，确定前缀内相对顺序则无法记录关键位上的限制。

考虑每一段内确定顺序，这样段内不会涉及到关键点的问题，段间合并由于 v_i 递增考虑延迟贡献。

方便起见令 p_0=0,p_{n+1}=n+1 为确定位，加入关键点范围。

在段内设 dp_{i,l,r} 表示处理完段内前 i 位的相对排名，这部分所有方案中满足 首位和末尾的相对排名分别为 l,r 的权值和，令 S 为段长，可以在 \mathcal O(S^2) 时间内处理出来。

设 L=S-2，段内值在 [1,v_i),(v_i,v_{i+1}),(v_{i+1},n] 内的元素个数分别 a,b,L-a-b，则 q_i,q_{i+1} 的段内排名分别为 a+1,a+b+2。

考虑立即确定前两种数的具体值，第三种先记录下个数放到以后确定。

于是设 f_{i,j} 表示处理完 [1,p_i] 部分，每一段内部确定相对顺序，且其中值在 [1,v_i] 的位具体值均已确定，还有 j 位值 >v_i 待定，这部分所有方案价值和。

但有段内顺序就关心每个段未确定的个数，故考虑在加入时乘一些系数使得前缀内相对顺序完全确定。

枚举 a,b 后，设 t=v_{i+1}-v_i-1,k=L-a-b，确定第一类数方案数为 \binom{v_i-(q_i-j)}{a}，第二类为 \binom{t}{b}，然后枚举 j 个数中值在 (v_i,v_{i+1}) 的个数 x，由于前面数相对关系已知，这 x 个数是确定的，只需要选出 x 个值以及将新产生的 k 个值和先前余下 j-x 个值的顺序归并。

直接做由于 (i,j) 对数 \mathcal O(n)，复杂度 \mathcal O(n^4)。

::::info[\mathcal O(n^4)代码]

//#include "ascend.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define IL inline
const int N = 505;
int C[N][N], fac[N], mod;
int f[N][N], dp[N][N], dp1[N][N];
IL void uadd(int &x, int y) {
  if ((x += y) >= mod) x -= mod;
}
int ascend(int c, int n, int __, vector<int> p, vector<int> w) {
  mod = __;
  for (int i = 0; i < N; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      f[i][j] = 0;
  fac[0] = 1;
  for (int i = 1; i < N; ++i)
    fac[i] = 1LL * fac[i - 1] * i % mod;
  vector<int> pos, val;
  pos.push_back(0); val.push_back(0);
  for (int i = 0; i < n; ++i)
    if (p[i]) pos.push_back(i + 1), val.push_back(p[i]);
  pos.push_back(n + 1); val.push_back(n + 1);
  int z = pos.size();
  f[0][0] = 1;
  for (int i = 0; i < z - 1; ++i) {
    int L = pos[i + 1] - pos[i] - 1, S = L + 2;
    int vm = val[i + 1] - val[i] - 1;
    for (int l = 0; l <= S; ++l)
      for (int r = 0; r <= S; ++r)
        dp[l][r] = 0;
    dp[1][1] = 1;
    for (int j = 1; j < S; ++j) {
      int _ = pos[i] - 1 + j;
      int W = _ == 0 || _ == n ? 1 : w[_ - 1];
      for (int l = 1; l <= j; ++l) {
        for (int r = 1; r <= j; ++r) {
          int t = dp[l][r], wt = 1LL * t * W % mod;
          if (!t) continue;
          for (int nr = 1; nr <= j + 1; ++nr)
            uadd(dp1[l + (nr <= l)][nr], nr <= r ? t : wt);
        }
      }
      for (int l = 1; l <= j + 1; ++l)
        for (int r = 1; r <= j + 1; ++r)
          dp[l][r] = dp1[l][r], dp1[l][r] = 0;
    }
    for (int j = 0; j <= pos[i]; ++j) {
      int t = f[i][j];
      int m = val[i] - (pos[i] - j);
      if (!t || m < 0) continue;
      for (int a = 0; a + 1 <= S; ++a) {
        for (int b = 0; a + b + 2 <= S; ++b) {
          int dpv = dp[a + 1][a + b + 2];
          int coef = 1LL * C[m][a] * C[vm][b] % mod * t % mod * dpv % mod;
          if (!coef) continue;
          for (int x = 0; x <= j && x <= vm - b; ++x) {
            int k = L - a - b, q = j - x + k;
            uadd(f[i + 1][q], 1LL * coef * C[vm - b][x] % mod * C[q][k] % mod);
          }
        }
      }
    }
  }
  return f[z - 1][0];
}

::::

接下来对着这个东西优化:

for (int j = 0; j <= pos[i]; ++j) {
  for (int a = 0; a + 1 <= S; ++a) {
    for (int b = 0; a + b + 2 <= S; ++b) {
      int coef = C[val[i] - pos[i] + j][a] * C[vm][b] * f[i][j] * dp[a + 1][a + b + 2];
      int k = L - a - b;
      for (int r = 0; r <= j; ++r)
        f[i + 1][r + k] += coef * C[vm - b][j - r] * C[r + k][k];
    }
  }
}

首先 a 需要枚举，令 g_{a,j}=f_{i,j}\binom{val_i-pos_i+j}{a}，贡献看作 f_{i+1,r+k}\leftarrow s_{a,b,r}\cdot \binom{r+k}{k}\binom{vm}{b}dp_{a+1,a+b+2}，其中 s_{a,b,r}=\sum_{j=r}^{pos_i} g_{a,j}\binom{vm-b}{j-r}，考虑利用 \binom{x}{y}=\binom{x+1}{y}-\binom{x}{y-1} 在其内部建立递推关系。

有 s_{a,b,r}=s_{a,b-1,r}-s_{a,b,r+1}，暴力求 s_{a,0,r} 再不断往上递推即 \mathcal O(n^3)。

::::info[\mathcal O(n^3) 代码]

//#include "ascend.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define IL inline
const int N = 505;
int C[N][N], mod;
int dp[N][N], sdp[N][N];
int g[N], f[N][N], s[N][N];
IL int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
IL int sub(int x, int y) { return x < y ? x + mod - y : x - y; }
IL void uadd(int &x, int y) { if ((x += y) >= mod) x -= mod; }
IL int c(int n, int m) { return n < m || m < 0 ? 0 : C[n][m]; }
int ascend(int ___, int n, int __, vector<int> p, vector<int> w) {
  mod = __;
  for (int i = 0; i < N; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
  }
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      f[i][j] = 0;
  vector<int> pos, val;
  pos.push_back(0); val.push_back(0);
  for (int i = 0; i < n; ++i)
    if (p[i]) pos.push_back(i + 1), val.push_back(p[i]);
  pos.push_back(n + 1); val.push_back(n + 1);
  int z = pos.size();
  f[0][0] = 1;
  for (int i = 0; i < z - 1; ++i) {
    int L = pos[i + 1] - pos[i] - 1, S = L + 2;
    int vm = val[i + 1] - val[i] - 1;
    for (int l = 0; l <= S; ++l)
      for (int r = 0; r <= S; ++r)
        dp[l][r] = sdp[l][r] = 0;
    dp[1][1] = sdp[1][1] = 1;
    for (int j = 2; j <= S; ++j) {
      int _ = pos[i] + j - 2;
      int W = _ == 0 || _ == n ? 1 : w[_ - 1];
      for (int l = 1; l <= j; ++l) {
        for (int r = 1, t, all; r <= j; ++r) {
          if (l == r) { dp[l][r] = 0; continue; }
          if (r < l) t = sdp[l - 1][r - 1], all = sdp[l - 1][j - 1];
          else t = sdp[l][r - 1], all = sdp[l][j - 1];
          dp[l][r] = add(1LL * t * W % mod, sub(all, t));
        }
      }
      for (int l = 1; l <= j; ++l)
        for (int r = 1; r <= j; ++r)
          sdp[l][r] = add(sdp[l][r - 1], dp[l][r]);
    }
    for (int a = 0; a <= L; ++a) {
      for (int j = 0; j <= pos[i]; ++j)
        g[j] = 1LL * f[i][j] * c(val[i] - pos[i] + j, a) % mod;
      for (int r = 0; r <= pos[i]; ++r)
        s[0][r] = 0;
      for (int r = 0; r <= pos[i]; ++r)
        for (int j = r; j <= pos[i]; ++j)
          uadd(s[0][r], 1LL * g[j] * c(vm, j - r) % mod);
      for (int b = 1; a + b <= L; ++b)
        for (int r = pos[i]; r >= 0; --r)
          s[b][r] = sub(s[b - 1][r], r == pos[i] ? 0 : s[b][r + 1]);
      for (int b = 0; a + b <= L; ++b) {
        int k = L - a - b;
        int coef = 1LL * c(vm, b) * dp[a + 1][a + b + 2] % mod;
        if (!coef) continue;
        for (int r = 0; r <= pos[i]; ++r)
          uadd(f[i + 1][r + k], 1LL * s[b][r] * c(r + k, k) % mod * coef % mod);
      }
    }
  }
  return f[z - 1][0];
}

::::