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

· · 题解

考虑容斥，选定若干个上升连续段，令段内都是递增排列的，然后对实际上是 q_i < q_{i + 1} 的位置 i，但是它在某个方案中被钦定为 q_i > q_{i + 1}，考虑用 -1 的系数容斥掉，这样的效果是，令 w_i \gets w_i - 1，然后我们就变成：选定若干连续段，每个连续段 [l, r] 有 \prod_{i = l}^{r - 1} w_i 的贡献，并且连续段中 q_i 递增。

考虑划分出来的连续段，有几种情况：

考虑提前钦定 trick，对于一个位置 i，只保留考虑不超过 p_{lst_i} 的所有数，对于剩下的数，我们将其视作“空位”，设计 dp，f_{i,j} 表示，按照上述定义，留下 j 个空位，同时把“若选定 j 个数填入这些空位的方案数”的系数也一并在转移时处理。

为了方便，我们分步转移，设置辅助数组 g，意义大致与 f 相同，但是只考虑 p_i \not = 0 的转移点 i（以下省略 \prod w_i）：

最后一步看起来是瓶颈，但是实际上，可以另设 h 数组，意义仍然与 f, g 相同，但是分两步，一步 f 到 h 转移前面填的位置，另一步 h 到 f 转移空位，复杂度 O(n^3)。 ::::info[代码]

// Think TWICE, code ONCE
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace qwq {
    const int N = 505;
    int n, ans, Mod, p[N], w[N], nxt[N], pre[N];
    int f[N][N], g[N][N], h[N][N], C[N][N], mul[N][N];
    inline void Add(int &x, int y) { x += y; if(x >= Mod) x -= Mod; }
    void Solve() {
        int i, j, k, t;
        memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g)), memset(h, 0, sizeof(h)), f[0][0] = 1;
        w[n++] = 1, p[n] = n;
        for(i = 1; i < n; i++) w[i] = (w[i] + Mod - 1) % Mod;
        for(i = 1; i <= n; i++) {
            mul[i][i] = 1;
            for(j = i + 1; j <= n; j++) mul[i][j] = 1ll * mul[i][j - 1] * w[j - 1] % Mod;
        }
        for(i = 0; i <= n; i++) {
            C[i][0] = 1;
            for(j = 1; j <= i; j++) C[i][j] = C[i - 1][j], Add(C[i][j], C[i - 1][j - 1]);
        }
        for(i = 1, pre[0] = 0; i <= n; i++) pre[i] = p[i] ? i : pre[i - 1];
        for(i = n, nxt[n + 1] = n + 1; i >= 0; i--) nxt[i] = p[i] ? i : nxt[i + 1];
        for(i = 0; i <= n; i++) for(j = 0; j <= i; j++) {
            int rem = p[pre[i]] - i + j;
            if(rem < 0) continue;
            if(nxt[i] == i && g[i][j]) {
                int val = 1ll * g[i][j] * mul[i][nxt[i + 1]] % Mod;
                for(t = 0; t <= j; t++) {
                    int x = p[nxt[i + 1]] - p[i] - 1, y = nxt[i + 1] - i - 1, z = j - t;
                    if(x >= y) Add(g[nxt[i + 1]][t], 1ll * val * C[x][y] % Mod * C[x - y][z] % Mod);
                }
                for(k = i; k < nxt[i + 1]; k++) {
                    Add(f[k][j + k - i], 1ll * g[i][j] * C[j + k - i][j] % Mod * mul[i][k] % Mod);
                }
            }
            for(k = i; k < nxt[i + 1]; k++) {
                Add(f[k][j + k - i], 1ll * h[i][j] * C[j + k - i][j] % Mod * mul[i][k] % Mod);
            }  
            if(f[i][j]) {
                for(k = i + 1; k < nxt[i + 1]; k++) {
                    int val = 1ll * f[i][j] * mul[i + 1][k] % Mod; 
                    Add(h[k][j], 1ll * val * C[rem][k - i] % Mod);
                    Add(f[k][j + k - i], 1ll * val * C[j + k - i][j] % Mod);
                }
                if(i < n) {
                    int val = 1ll * f[i][j] * mul[i + 1][nxt[i + 1]] % Mod;
                    for(t = 0; t <= j + nxt[i + 1] - i - 1; t++) {
                        Add(g[nxt[i + 1]][t], 1ll * val * C[p[nxt[i + 1]] - p[pre[i]] - 1][j - t] % Mod * C[rem + p[nxt[i + 1]] - p[pre[i]] - 1 - (j - t)][nxt[i + 1] - 1 - i] % Mod);
                    }
                }
            }
        }
        ans = f[n][0];
    }
}
int ascend(int c, int n, int m, vector<int> p, vector<int> w) {
    int i; qwq::n = n, qwq::Mod = m;
    for(i = 1; i <= n; i++) qwq::p[i] = p[i - 1];
    for(i = 1; i < n; i++) qwq::w[i] = w[i - 1];
    qwq::Solve(); return qwq::ans;
}

::::