F2. 小排列问题（困难版）

详细题解

一、问题转化

将排列 $p$ 看作 $n\times n$ 网格上的 $n$ 个棋子，第 $i$ 行的棋子在列 $p_i$。
条件 $a_i$ 表示：在子网格 $[1,i]\times[1,i]$（前 $i$ 行且前 $i$ 列）中恰好有 $a_i$ 个棋子（若 $a_i\neq -1$）。

如果 $a_n\neq -1$ 且 $a_n\neq n$，则不可能满足条件（因为整个 $n\times n$ 网格中恰好有 $n$ 个棋子，且都在前 $n$ 行前 $n$ 列），答案为 $0$。
如果 $a_n=-1$，我们可以强制 $a_n=n$，因为整个网格必须恰好包含所有 $n$ 个棋子，这个条件自动成立。
因此，在输入中若 $a_n=-1$，我们将其改为 $n$；若 $a_n$ 为其他值且不等于 $n$，直接输出 $0$。

二、必要条件

考虑所有 $a_i\neq -1$ 的位置，设它们为 $i_1 < i_2 < \dots < i_m$，并补充 $i_0=0$，$a_{i_0}=0$。
由于子网格 $[1,i_k]\times[1,i_k]$ 包含 $[1,i_{k-1}]\times[1,i_{k-1}]$，因此必须有：

$$0 = a_{i_0} \le a_{i_1} \le a_{i_2} \le \dots \le a_{i_m} = n, $$

且每个 $a_{i_k} \le i_k$。
若上述非递减条件不成立，答案为 $0$。

三、组合计数

对于相邻的两个非 $-1$ 位置 $j = i_{k-1}$ 和 $i = i_k$，已知在 $[1,j]\times[1,j]$ 中已有 $a_j$ 个棋子。
我们可以在不改变计数的情况下，将这些棋子重新标号，使得它们恰好占据前 $a_j$ 行和前 $a_j$ 列（即位置 $(1,1),(2,2),\dots,(a_j,a_j)$）。
现在需要再放入 $d = a_i - a_j$ 个新棋子，使得子网格 $[1,i]\times[1,i]$ 中总共有 $a_i$ 个棋子。

新棋子必须放在 $[1,i]\times[1,i]$ 中尚未被占用的格子。
未被占用的行：共有 $i$ 行，但前 $a_j$ 行已被占用（每行已有一个棋子），不过这些行中仍有空列（列 $>a_j$）可以放新棋子，因此所有 $i$ 行都是可用的。
未被占用的列：前 $a_j$ 列已被占用，但列 $a_j+1$ 到 $i$ 是空的，共 $i - a_j$ 列。
实际上，更准确的分析是：新棋子的行可以来自所有 $i$ 行，列只能来自后 $i - a_j$ 列？不对，因为新棋子也可以放在前 $a_j$ 行的后 $i-a_j$ 列中。
经典结论（可通过组合对射证明）：在已有 $a_j$ 个棋子占据前 $a_j$ 行和前 $a_j$ 列的前提下，在 $[1,i]\times[1,i]$ 中再放 $d$ 个棋子使得每行每列至多一个棋子的方案数为：

$$\binom{i - a_j}{d}^2 \cdot d!.$$

解释：从剩余的空闲行（共 $i - a_j$ 行）中选出 $d$ 行，从空闲列（共 $i - a_j$ 列）中选出 $d$ 列，然后将这 $d$ 行与 $d$ 列一一匹配（$d!$ 种方式）。
注意：这里“空闲行”是指前 $a_j$ 行之外的行吗？实际上，前 $a_j$ 行已经有一个棋子，但它们还可以再放新棋子吗？不行，因为每行只能有一个棋子。所以前 $a_j$ 行不能再放新棋子。因此空闲行正是 $a_j+1$ 到 $i$ 这 $i-a_j$ 行。空闲列也是 $a_j+1$ 到 $i$ 这 $i-a_j$ 列。而新棋子必须同时位于空闲行和空闲列的交集（一个 $(i-a_j)\times(i-a_j)$ 的正方形）中。因此从该正方形中选 $d$ 行 $d$ 列再匹配，就是 $\binom{i-a_j}{d}^2 d!$。
如果允许新棋子放在前 $a_j$ 行但后 $i-a_j$ 列，那么就会与已有棋子冲突（同行），所以不行。因此上述解释正确。

四、最终公式

对所有相邻的非 $-1$ 位置（包括虚拟的 $j=0,a_0=0$）乘以上述值，得到答案：

$$\text{ans} = \prod_{k=1}^{m} \left( \binom{i_k - a_{i_{k-1}}}{a_{i_k} - a_{i_{k-1}}}^2 \cdot (a_{i_k} - a_{i_{k-1}})! \right) \pmod{998244353}. $$

五、算法实现

1. 预处理阶乘 $fact[i]$ 和逆元 $invfact[i]$ 到 $2\cdot10^5$，用于快速计算组合数。
2. 对于每个测试用例：
   • 读入 $n$ 和数组 $a$（下标从 $1$ 开始）。
   • 若 $a_n \neq -1$ 且 $a_n \neq n$，输出 $0$ 并跳过。
   • 否则令 $a_n = n$。
   • 初始化 $prev = 0$（上一个非 $-1$ 的 $a$ 值），$ans = 1$。
   • 遍历 $i = 1$ 到 $n$：
     • 若 $a_i = -1$，跳过。
     • 若 $a_i < prev$ 或 $a_i > i$，则答案 $=0$ 并结束。
     • 令 $d = a_i - prev$，$free = i - prev$。
     • $ans = ans \times \binom{free}{d}^2 \times fact[d] \pmod{MOD}$。
     • 更新 $prev = a_i$。
   • 输出 $ans$。

六、时间复杂度

每个测试用例 $O(n)$，总复杂度 $O(\sum n)$，满足题目限制。

---

C++ 代码实现

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

const int MOD = 998244353;
const int MAXN = 200005;

long long fact[MAXN], invfact[MAXN];

long long modpow(long long a, long long e) {
    long long res = 1;
    while (e) {
        if (e & 1) res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    invfact[MAXN-1] = modpow(fact[MAXN-1], MOD-2);
    for (int i = MAXN-2; i >= 0; i--) invfact[i] = invfact[i+1] * (i+1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    if (a[n] != -1 && a[n] != n) {
        cout << "0\n";
        return;
    }
    a[n] = n; // 强制最后一个为 n
    
    long long ans = 1;
    int prev = 0; // 上一个非 -1 的 a 值
    for (int i = 1; i <= n; i++) {
        if (a[i] == -1) continue;
        if (a[i] < prev || a[i] > i) {
            cout << "0\n";
            return;
        }
        int d = a[i] - prev;
        int free = i - prev;
        ans = ans * C(free, d) % MOD * C(free, d) % MOD * fact[d] % MOD;
        prev = a[i];
    }
    cout << ans << '\n';
}

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