P17693 题解

_constexpr_int_ · 2026-10-21 15:54:31 · 题解

一开始想的是维护 f_i 表示插了 1\sim n 的方案数，然后调转移的时候你会发现这样是没有前途的，因为 y_v 在哪个位置不好维护。

注意到可以满足 \max_{j \in [1,i)} a_i \ge y_v 的条件，考虑多维护一个前缀最大值，即设填了 i 个数，前缀最大值为 j 的方案数为 f_{i,j}，则分前缀最大值变和不变写出转移是简单的，复杂度 \mathcal O(n^3)。

先考虑优化前缀最大值变的情况，本来的式子是 f_{i+1,v} \gets f_{i+1,v}+f_{i,j}，你考虑对于每一个 f_{i+1,v}，观察有哪些 f_{i,j} 是可以对其产生贡献的，把条件写出来发现总贡献就是 \sum\limits_{k=y_v}^{v-1} f_{i,k}，前缀和优化这个东西这一部分可以做到 \mathcal O(n^2)。

再考虑优化前缀最大值不变的情况，维护一个 c 表示当前已转移的数量，本来的式子是 f_{i+1,j} \gets f_{i+1,j}+(c-i)f_{i,j}，考虑把 x_v 丢到桶里然后差分维护这个东西，每次拿出 i+1 对应的桶在差分上更新其对 [\max(v,y_v),v) 的贡献即可，转移的时候顺便把前缀和一起统计了可以让这一部分做到 \mathcal O(n^2)，空间的话上滚动数组可以做到线性。

constexpr int Maxn = 5e3 + 5;
constexpr int Mod = 998244353;

inline void Add(int &x, int y) { x += y; if (x >= Mod) x -= Mod; }

int x[Maxn], y[Maxn];
int f[2][Maxn], diff[Maxn], pre[Maxn];
vector <int> tg[Maxn];

void Main() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x[i];
    tg[x[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    cin >> y[i];
    diff[max(i, y[i])]++;
  }
  f[0][0] = 1;
  for (int i = 0; i < n; i++) {
    int u = i & 1;
    memset(f[u ^ 1], 0, sizeof f[u ^ 1]);
    for (int v : tg[i + 1]) {
      diff[max(v, y[v])]--;
      diff[v]++;
    }
    pre[0] = f[u][0]; int cnt = 0;
    for (int j = 1; j <= n; j++) {
      cnt += diff[j];
      Add(f[u ^ 1][j], 1ll * (cnt - i) * f[u][j] % Mod);
      pre[j] = (pre[j - 1] + f[u][j]) % Mod;
    }
    for (int v = 1; v <= n; v++) {
      if (y[v] > v - 1 && i + 1 < x[v]) continue;
      Add(f[u ^ 1][v], i + 1 >= x[v] ? pre[v - 1] : (pre[v - 1] - pre[y[v] - 1] + Mod) % Mod);
    }
  }
  cout << f[n & 1][n] << '\n';
  for (int i = 0; i < 2; i++)
    for (int j = 0; j <= n; j++) f[i][j] = 0;
  for (int i = 1; i <= n; i++) tg[i].clear();
  for (int i = 0; i <= n; i++) {
    pre[i] = diff[i] = 0;
  }
}