D. 排列黑洞 题解

---

题意回顾

给定不完整的染色序列 $s$（某些 $s_i=-1$ 待定），求能生成该序列的排列 $p$ 的数量。染色过程见题目描述。

---

过程转化与区间 DP

将整个过程倒过来考虑：全黑时最终状态，每个格子 $i$ 的分数 $s_i$ 等于它在被染黑后作为“最近黑格”被其他格子选中的次数。正向看，第 $1$ 次染色不加分；之后的 $n-1$ 次每次给当时最近的黑格加 $1$。

假设我们固定某个区间 $[l,r]$，且已知在染色该区间内任何一个格子之前，$l-1$ 和 $r+1$ 已经是黑色的（若存在）。那么区间内第一个被染色的点 $i$ 必然选择 $l-1$ 和 $r+1$ 中较近的一个进行加分（距离相等时选编号小的，即 $l-1$）。此后 $i$ 变黑，将区间划分为 $[l,i-1]$ 和 $[i+1,r]$，这两部分又面临类似的问题，只是外侧的黑格发生了变化：左子区间的右外侧是 $i$，右子区间的左外侧也是 $i$。

这启发我们使用区间 DP。
定义状态：$dp[l][r][x][y]$ 表示考虑区间 $[l,r]$ 被染色的所有合法排列方案数，满足：

• 在该区间染色过程中，$s_{l-1}$ 额外增加了 $x$；
• $s_{r+1}$ 额外增加了 $y$。

这里“额外增加”指的是区间内部的点染色时选择 $l-1$ 或 $r+1$ 作为最近黑格的总次数。
区间内部点的分数在递归到更小的子区间时会体现为其外侧格子的 $x$ 或 $y$ 贡献。

最终答案：整个序列 $[1,n]$ 没有外侧黑格，故要求 $x=0,y=0$。若 $l=1$，则 $x$ 只能为 $0$；$r=n$ 时 $y$ 只能为 $0$。
答案即为 $dp[1][n][0][0]$。

---

转移方程

对于区间 $[l,r]$，枚举该区间内第一个被染色的点 $i$（$l\le i\le r$）。
$i$ 选择给 $l-1$ 还是 $r+1$ 加分，取决于距离比较：

• 若 $i-l+1 \le r+1-i$（即 $i\le \left\lfloor\frac{l+r}{2}\right\rfloor$），则 $i$ 给 $l-1$ 加 $1$ 分，体现为 $x\ge 1$ 时从 $x-1$ 转移；
• 否则 $i$ 给 $r+1$ 加 $1$ 分，体现为 $y\ge 1$ 时从 $y-1$ 转移。

设左子区间 $L=[l,i-1]$，右子区间 $R=[i+1,r]$。
在 $L$ 中，$i$ 作为右外侧黑格，会获得来自 $L$ 的贡献 $y'$（即 $dp[L][*][y']$ 中的 $y'$）；
在 $R$ 中，$i$ 作为左外侧黑格，会获得来自 $R$ 的贡献 $x'$（即 $dp[R][x'][*]$ 中的 $x'$）。
因此 $i$ 最终的分数 $s_i = y' + x'$。若题目中 $s_i$ 已经固定，则必须满足 $s_i = y' + x'$；否则任意非负整数均可。

此外，$i$ 选为第一个后，左右区间的染色顺序可以任意交错，只需保持各自内部顺序。区间总共有 $len = r-l$ 个点（除 $i$ 外），左区间有 $lenL = i-l$ 个，右区间有 $lenR = r-i$ 个。排列顺序的方案数要乘上组合数 $C(len,\ lenL)$ 以选定左区间点出现的时机。

综上，转移方程为（省略边界细节）：

若 $s_i = -1$：

$$\begin{aligned} &dp[l][r][x][y] = \\ &\sum_{\substack{i\le \lfloor(l+r)/2\rfloor \\ x\ge 1}} \binom{r-l}{i-l} \sum_{j,k} dp[l][i-1][x-1][j] \cdot dp[i+1][r][k][y] \\ &+ \sum_{\substack{i > \lfloor(l+r)/2\rfloor \\ y\ge 1}} \binom{r-l}{i-l} \sum_{j,k} dp[l][i-1][x][j] \cdot dp[i+1][r][k][y-1] \end{aligned} $$

若 $s_i = v$ 固定：

$$\begin{aligned} &dp[l][r][x][y] = \\ &\sum_{\substack{i\le \lfloor(l+r)/2\rfloor \\ x\ge 1}} \binom{r-l}{i-l} \sum_{\substack{j,k \\ j+k=v}} dp[l][i-1][x-1][j] \cdot dp[i+1][r][k][y] \\ &+ \sum_{\substack{i > \lfloor(l+r)/2\rfloor \\ y\ge 1}} \binom{r-l}{i-l} \sum_{\substack{j,k \\ j+k=v}} dp[l][i-1][x][j] \cdot dp[i+1][r][k][y-1] \end{aligned} $$

边界条件：

• 当 $l>r$ 时，空区间仅 $dp[l][r][0][0]=1$，其余为 $0$。
• 当 $l=1$ 时，左边没有 $l-1$，强制 $x=0$；当 $r=n$ 时，强制 $y=0$。
• 所有 $x,y$ 以及中间枚举的 $j,k$ 都有取值范围，且不能超过 $n$，实际上有更紧的上界。

---

关键性质：分数上界为 $O(\log n)$

证明：固定位置 $i$，考虑左侧的那些会给 $i$ 加分的格子 $c_1 < c_2 < \dots < c_k < i$。
对于相邻两个这样的格子 $c_j < c_{j+1}$，在 $c_{j+1}$ 被染色时，$i$ 必须是最近的黑色格子（因为 $c_j$ 当时尚未染色，是白色）。
此时 $i$ 与 $c_{j+1}$ 的距离为 $i - c_{j+1}$。若 $c_j$ 已经被染色（它会在 $c_{j+1}$ 之后才染色），则 $c_j$ 也是黑色，且更近？但 $c_{j+1}$ 染色时 $c_j$ 还是白的，所以不构成干扰。然而，在 $c_j$ 染色时，$i$ 也必须还是最近的黑色格子（否则 $c_j$ 不会给 $i$ 加分）。因此有：

$$i - c_j > 2(i - c_{j+1})$$

否则，若 $i - c_j \le 2(i - c_{j+1})$，则 $c_{j+1}$ 会更靠近 $c_j$ 而不是 $i$，导致 $c_j$ 给 $c_{j+1}$ 加分而非 $i$。
由此可得每个这样的格子到 $i$ 的距离至少翻倍，因此数量 $k = O(\log n)$。右侧同理。
所以 $s_i = O(\log n)$。
实际 $n\le 100$，$\log_2 100 \approx 7$，故 $x,y,j,k$ 的上限可设为 $\lceil \log_2 n \rceil + 1 \approx 8$。

---

复杂度分析

• 状态数：$O(n^2 \cdot \log^2 n)$，约 $100^2 \times 8^2 \approx 6.4\times 10^5$。
• 转移：枚举 $i$ 和 $j,k$（范围 $O(\log n)$），复杂度 $O(n^3 \cdot \log^3 n)$，约 $10^6 \times 512 = 5\times 10^8$，实际常数小且很多状态不可达，可在 $3$ 秒内通过。

---

实现细节

1. 预处理组合数 $C_{i}^{j}$ 模 $998244353$。
2. DP 数组用 int 或 long long，注意取模。
3. 设置 $M = \lceil \log_2 n \rceil + 2$ 作为 $x,y$ 上限。
4. 边界：当 $l=1$ 时只处理 $x=0$；$r=n$ 时只处理 $y=0$。
5. 转移时注意 $x-1$ 或 $y-1$ 不能越界。
6. 对于 $s_i$ 固定的情况，需匹配 $j+k = s_i$，且 $j,k$ 均 $\le M$。
7. 空区间 $l>r$ 返回 $x=0,y=0$ 时为 $1$。

---

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 105;
const int MAXLOG = 9; // log2(100) ≈ 7, 取9足够

int n;
vector<int> s;
int C[MAXN][MAXN];
int dp[MAXN][MAXN][MAXLOG][MAXLOG];
bool vis[MAXN][MAXN][MAXLOG][MAXLOG];

void add(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

int mul(int a, int b) {
    return 1LL * a * b % MOD;
}

// 记忆化搜索
int solve(int l, int r, int x, int y) {
    if (l > r) {
        return (x == 0 && y == 0) ? 1 : 0;
    }
    // 边界：左右外侧不存在时，对应分数必须为0
    if (l == 1 && x != 0) return 0;
    if (r == n && y != 0) return 0;
    if (x < 0 || y < 0) return 0;
    if (x >= MAXLOG || y >= MAXLOG) return 0; // 超出范围不可能
    if (vis[l][r][x][y]) return dp[l][r][x][y];
    vis[l][r][x][y] = true;
    int &res = dp[l][r][x][y] = 0;

    int len = r - l; // 除了i之外的节点数
    for (int i = l; i <= r; ++i) {
        int leftLen = i - l;
        int rightLen = r - i;
        int ways = C[len][leftLen]; // 选择左边点出现的位置
        if (i <= (l + r) / 2) { // 给左边加分，需要x >= 1
            if (x < 1) continue;
            for (int j = 0; j < MAXLOG; ++j) { // 左区间对i的加分（dp[l][i-1]的y）
                for (int k = 0; k < MAXLOG; ++k) { // 右区间对i的加分（dp[i+1][r]的x）
                    if (s[i] != -1 && j + k != s[i]) continue;
                    int leftWays = solve(l, i - 1, x - 1, j);
                    int rightWays = solve(i + 1, r, k, y);
                    if (leftWays && rightWays) {
                        add(res, mul(ways, mul(leftWays, rightWays)));
                    }
                }
            }
        } else { // 给右边加分，需要y >= 1
            if (y < 1) continue;
            for (int j = 0; j < MAXLOG; ++j) {
                for (int k = 0; k < MAXLOG; ++k) {
                    if (s[i] != -1 && j + k != s[i]) continue;
                    int leftWays = solve(l, i - 1, x, j);
                    int rightWays = solve(i + 1, r, k, y - 1);
                    if (leftWays && rightWays) {
                        add(res, mul(ways, mul(leftWays, rightWays)));
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 组合数预处理
    for (int i = 0; i < MAXN; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        s.resize(n + 1);
        for (int i = 1; i <= n; ++i) cin >> s[i];

        memset(vis, 0, sizeof(vis));
        int ans = solve(1, n, 0, 0);
        cout << ans << "\n";
    }
    return 0;
}

总结

本题将染色过程转化为递归的“区间选根”模型，利用区间 DP 计数，并通过分数的对数级上界压缩状态，在 $O(n^3\log^3 n)$ 内求解。