题解：P16433 [APIO 2026 中国赛区] 上升

· · 题解

直接算贡献并不容易，考虑只要求 S(q) 的一个子集 T 满足条件，由于 f(q) = \prod\limits_{i\in S(q)}{(w_i - 1 + 1)} = \sum\limits_{T \subseteq S} {\prod\limits_{i\in T}{(w_i - 1)}}，故我们将所有 w_i 减去 1 即可。

下文称标记点为该位置上的值确定的点。

考虑我们要求一定上升的一个段，若这个段中有超过 2 个标记点，我们可以将其划分为若干个标记点个数 \le 2 的段。具体的，考虑标记点和左右端点构成的序列，取相邻两个作为新的段即可。（下图中黑色为这个段，红色为标记点，蓝色为新段）

那么我们只要考虑相邻标记点之间的上升段，设这两个标记点的值为 [p, q]，我们关心的值有 3 个，分别是：(0, p) 的数用了几个；(p, q) 的数用了几个；(q, n] 的数用了几个。每对标记点所需的信息都不一样，所以如果直接记录离不开状压。

称一对相邻标记点为一个段。

考虑延迟钦定，设 f_{i,j} 表示前 i 个段比右端点大的数的个数 j，且这些数内部的值域顺序已经确定的权值和。在从 (p, q) 到 (q, r) 时把 (p, q) 填入。此时段内有记录 \operatorname{count}(0,q),\operatorname{count}(q,r),\operatorname{count}(r,n+1) 的朴素 dp。由于三数之和为 i，所以状态数实际是 \mathcal O(n^3) 的。可以分步转移优化做到 \mathcal O(n^4)。

但是 \operatorname{count}(q,r) 其实是我们为了转移方便人为加入的状态，在段间转移其实并不必须完全记录。考虑将这一步提到最后再做，只记录 \operatorname{count}(0,q),\operatorname{count}(q,n+1)。最后枚举 (p,q) 中选择多少个并乘上组合数转移到 f_{i, j} 即可。再配合上分步转移，此时时间复杂度为 \mathcal O(n^3)。

rep (i, 0, n + 1) {
    t[i][i] = 1;
    rep (j, i, n) t[i][j + 1] = 1LL * t[i][j] * w[j] % mod;
  }
  dp[0][0] = 1;
  auto work = [&](int L, int R) {
    int p = a[L], q = a[R];
    memset(f[L], 0, sizeof f[L]);
    rep (i, L + 1, R) rep (j, 0, i) {
      if (p + 1 + j >= i && i < R) rep (k, L + 1, i) {
        int U = 1ULL * dp[k - 1][j] * C[p + 1 - k + j][i - k + 1] % mod * t[k][i] % mod;
        inc(dp[i][j], U), inc(f[i][j], U);
      }
      if (i < R) {
        int _u = (i - j <= L ? L : i - j + 1);
        if (_u == L) dp[i][j] = (dp[i][j] + 1ULL * dp[L][j - i + L] * t[L][i] % mod * C[j][j - i + L]) % mod;
        rep (k, max(L + 1, _u), i) {
          dp[i][j] = (dp[i][j] + (1ULL * dp[k - 1][j - i + k - 1] * t[k][i] 
            + 1ULL * f[k - 1][j - i + k - 1] * t[k - 1][i]) % mod * C[j][i - k + 1]) % mod;
        }
      } else {
        int _u = max(i - q + p, L), les, val;
        if (_u > L) ++ _u;
        if (_u == L) {
          les = q - p - i + L;
          val = 1ULL * dp[L][j] * t[L][i] % mod * C[q - p - 1][i - L - 1] % mod;
          rep (t, 0, min(j, les)) dp[R][j - t] = (dp[R][j - t] + 1ULL * val * C[les][t]) % mod;
        }
        rep (k, max(L + 1, _u), i) {
          val = (1ULL * f[k - 1][j] * t[k - 1][i] + 1ULL * dp[k - 1][j] * t[k][i]) % mod * C[q - p - 1][i - k] % mod;
          les = q - p - 1 - i + k;
          rep (t, 0, min(j, les)) dp[R][j - t] = (dp[R][j - t] + 1ULL * val * C[les][t]) % mod;
        }
      }
    }
  };