题解

题意简述

给定一个部分缺失（用 $-1$ 表示）的排列 $a$（元素为 $0 \sim n-1$ 的排列），需要将所有 $-1$ 填充为剩余数字，得到所有可能的合法排列。
定义排列的值为所有非空连续子段的 $\operatorname{mex}$ 之和。
求所有可能排列的值的总和，对 $10^9+7$ 取模。

---

思路分析

1. 转化 $\operatorname{mex}$ 的贡献

对于一段区间 $[i,j]$，$\operatorname{mex}([a_i \dots a_j])$ 等于最小的非负整数 $x$ 使得 $x$ 不在该区间中出现。
这等价于：对于每个 $x$，如果 $0 \sim x-1$ 全都出现在区间中，则 $x$ 对 $\operatorname{mex}$ 有贡献 $1$。
所以：

$$\operatorname{mex}([i,j]) = \sum_{x=0}^{n-1} [\text{$0 \sim x$ 全都出现在 $[i,j]$}] $$

（这里 $x$ 从 $0$ 到 $n-1$ 求和，但实际上当 $x$ 超过区间的长度时自动为 0）

---

2. 整体计数框架

设所有排列总数为 $t!$，其中 $t$ 是 $-1$ 的数量。
我们要求：

$$\sum_{\text{所有排列}} \sum_{1\le i\le j\le n} \operatorname{mex}([i,j]) $$

交换求和顺序：

$$\sum_{1\le i\le j\le n} \sum_{\text{所有排列}} \operatorname{mex}([i,j]) $$

再对每个固定 $x$（$0\le x<n$）统计：有多少排列使得 $[i,j]$ 包含 $0\sim x$ 全部。

---

3. 固定 $i,j,x$ 的计数

设：

• 在固定区间 $[i,j]$ 中，有 $c_1$ 个 $-1$ 位置。
• 在 $0\sim x$ 中，有 $c_2$ 个数字没有在 $a$ 的已知位置中出现（即这些数字需要被填入该区间中的 $-1$ 中）。
• 剩下 $t-c_2$ 个 $-1$ 在区间外，它们必须填入 $0\sim x$ 之外的数字。

则方案数为：

1. 从 $c_1$ 个区间内 $-1$ 中选出 $c_2$ 个位置来放这 $c_2$ 个特定数字：$\binom{c_1}{c_2}$。
2. 这 $c_2$ 个数字可以任意排列在这 $c_2$ 个位置上：$c_2!$。
3. 剩下的 $t-c_2$ 个 $-1$（区间外）任意排列剩下的 $t-c_2$ 个数字：$(t-c_2)!$。

所以贡献为：

$$\binom{c_1}{c_2} \cdot c_2! \cdot (t-c_2)!$$

注意：要求区间 $[i,j]$ 必须包含所有 $0\sim x$ 中已知出现的数字，即已知数字的位置必须在 $[i,j]$ 内，否则方案数为 0。

---

4. 高效枚举

直接枚举 $i,j,x$ 是 $O(n^3)$，不可行。
我们观察到 $x$ 只影响 $c_2$（需填充的数字数量），而 $c_2$ 取决于 $[i,j]$ 是否包含所有已知的 $0\sim x$。

定义：

• $b[pos]$ 为前缀中 $-1$ 的数量。
• 对每个区间 $[i,j]$，记 $x_0 = \min\{\text{不在区间中的已知数字}\}$，如果所有已知数字都在区间内，则 $x_0 = n$。
• 则对于 $x < x_0$，$c_2 = \text{在 $0\sim x$ 中未出现的数字数}$，它只依赖于$x$，与$[i,j]$ 无关。
• 对于 $x \ge x_0$，区间不包含所有 $0\sim x$，贡献为 0。

因此，我们可以先统计所有区间 $[i,j]$，对每个区间计算 $x_0$ 和区间内 $-1$ 的数量 $c_1$，然后对 $x = 0 \dots x_0-1$ 分别加上 $\binom{c_1}{c_2(x)} \cdot c_2(x)! \cdot (t-c_2(x))!$ 的贡献。

但这样还是 $O(n^3)$。优化：按 $c_1$ 和 $x$ 分组累加。

---

5. 差分优化

设 $d[c_1][x]$ 表示“区间内 $-1$ 数量为 $c_1$，且 $x_0 > x$”的区间数量。
则 $d[c_1][x]$ 对 $x$ 的贡献为：

$$\binom{c_1}{c_2(x)} \cdot c_2(x)! \cdot (t-c_2(x))! $$

其中 $c_2(x)$ = 在 $0\sim x$ 中未出现的数字数量（全局常数，可预处理）。

我们如何得到 $d[c_1][x]$？
对每个区间 $[i,j]$：

• 计算 c_1 = \text{区间内 -1 的数量}。
• 计算 $x_0 = \min\{ \text{不在区间内的已知数字} \}$（若全部在，则 $x_0=n$）。
• 则该区间对 $d[c_1][0], d[c_1][1], \dots, d[c_1][x_0-1]$ 各加 1。

这可以用差分数组实现：对每个 $c_1$，维护一个差分数组 $diff[x]$，对区间 $[0, x_0-1]$ 加 1，即：

$$diff[0] \mathrel{+}= 1,\quad diff[x_0] \mathrel{-}= 1 $$

最后前缀和得到 $d[c_1][x]$。

---

6. 枚举区间

我们要快速枚举所有 $[i,j]$ 并求出 $c_1$ 和 $x_0$。

• $c_1$ 可用前缀和 $b$ 轻松得到。

• $x_0$：已知数字的最小不在区间内的值。
  可以分别从左到右和从右到左维护前缀最小缺失值。具体方法：

  枚举左端点 $i$，从右往左扫描 $j$，维护两个值：

  • $mn_1$：左边部分（$1 \sim i-1$）已知数字的最小值（实际是“不在 $[i,j]$ 中的已知数字”需要看两端）。 更简单的做法： 设 $mn_1$ = 已知数字在 $i$ 左侧的最小值，$mn_2$ = 已知数字在 $j$ 右侧的最小值。
    则不在区间内的已知数字的最小值 = $\min(mn_1, mn_2)$。
    但 $mn_2$ 在 $j$ 向左移动时更新，$mn_1$ 固定对固定 $i$。

  算法：

  • 预处理每个位置右边已知数字的最小值 $min\_right[pos]$。
  • 枚举 $i$，设 $min\_left = n$（表示左侧无已知数字）。
  • 从 $j=n$ 向下到 $i$：
    • 更新 $min\_right$（若 $a_j$ 不是 -1，则 $min\_right$ 更新为 $\min(min\_right, a_j)$）。
    • $x_0 = \min(min\_left, min\_right)$。
    • $c_1 = b[j]-b[i-1]$。
    • 对 $d[c_1][0..x_0-1]$ 差分加 1。
  • 如果 $a_i$ 不是 -1，更新 $min\_left = \min(min\_left, a_i)$。

---

7. 最终计算

预处理：

• 阶乘 $fac[i]$。
• 组合数 $C[n][m]$。
• $cnt[x]$ = $0\sim x$ 中未出现的已知数字个数（$cnt[x] = x+1 - \text{已知的 } \le x \text{ 的数字数}$）。

则： [ \text{ans} = \sum_{x=0}^{n-1} \sum_{c_1 = cnt[x]}^{t} d[c_1][x] \cdot \binom{c_1}{cnt[x]} \cdot fac[cnt[x]] \cdot fac[t-cnt[x]] \pmod{mod} ] 因为当 $c_1 < cnt[x]$ 时，无法放下所有需要的数字，贡献为 0。

---

复杂度

• 枚举所有 $i,j$：$O(n^2)$。
• 差分与求和：$O(n^2)$。
• 总复杂度 $O(n^2)$，对 $n \le 5000$ 可行。

---

代码

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

const int maxn = 5050;
const int mod = 1000000007;

int n, a[maxn], fac[maxn], C[maxn][maxn], b[maxn], d[maxn][maxn];
bool vis[maxn];

void solve() {
    cin >> n;
    for (int i = 0; i <= n; ++i) {
        vis[i] = 0;
        for (int j = 0; j <= n; ++j) d[i][j] = 0;
    }
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        fac[i] = 1LL * fac[i - 1] * i % mod;
        b[i] = b[i - 1] + (a[i] == -1);
        if (a[i] != -1) vis[a[i]] = 1;
    }
    // 组合数
    for (int i = 0; i <= n; ++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 mn1 = n; // 左侧已知数字的最小值
    for (int i = 1; i <= n; ++i) {
        int mn2 = n; // 右侧已知数字的最小值
        for (int j = n; j >= i; --j) {
            int x = b[j] - b[i - 1];          // c1
            int y = min(mn1, mn2);            // x0
            d[x][0] = (d[x][0] + 1) % mod;
            d[x][y] = (d[x][y] - 1 + mod) % mod;
            if (a[j] != -1) mn2 = min(mn2, a[j]);
        }
        if (a[i] != -1) mn1 = min(mn1, a[i]);
    }
    // 前缀和得到 d[c1][x]
    for (int i = 0; i <= b[n]; ++i)
        for (int j = 1; j <= n; ++j)
            d[i][j] = (d[i][j] + d[i][j - 1]) % mod;
    int ans = 0, cnt = 0;
    for (int x = 0; x < n; ++x) {
        cnt += (!vis[x]);                     // c2 = cnt
        for (int c1 = cnt; c1 <= b[n]; ++c1) {
            ans = (ans + 1LL * C[c1][cnt] * fac[cnt] % mod 
                    * fac[b[n] - cnt] % mod * d[c1][x]) % mod;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}