感觉这个题还是挺不错的。
考虑 F1。考察 \(a_i\) 差分后的意义，发现 \(a_i - a_{i - 1}\) 就是 \((\sum\limits_{j = 1}^{i - 1} [p_j = i]) + p_i \le i\)。
考虑将其转化为棋盘问题。在 \((i, p_i)\) 放一个车，那么 \(a_i - a_{i - 1}\) 就是 \((1, i) \sim (i, i)\) 和 \((i, 1) \sim (i, i - 1)\) 这些格子组成的“L”字形的车的数量。
一个放车的方案合法当且仅当所有车互不攻击。因此容易发现合法的 \(a_i - a_{i - 1}\) 一定 \(\in [0, 2]\)。考虑从前往后扫，同时维护答案 \(ans\) 和现在还没被占用的行（列）数量 \(t\)。
- 若 \(a_i = a_{i - 1}\)，无事发生，多了第 \(i\) 行和列没被占用，因此 \(t \gets t + 1\)。
- 若 \(a_i - a_{i - 1} = 1\)，相当于可以在 \((1, i) \sim (i - 1, i)\) 和 \((i, 1) \sim (i, i - 1)\) 中还没被占用的格子放车，同时也可以在 \((i, i)\) 放车，那么 \(ans \gets ans \times (2t + 1)\)，\(t\) 不变。
- 若 \(a_i - a_{i - 1} = 2\)，\((1, i) \sim (i - 1, i)\) 和 \((i, 1) \sim (i, i - 1)\) 中还没被占用的格子各放一个车，那么 \(ans \gets ans \times t^2\)，然后 \(t \gets t - 1\)。
如上讨论可以通过 F1。
F2 我们继续将其放到棋盘上考虑。考虑一个 \(a_i \ne -1\) 的位置 \(i\)，设它上一个 \(a_j \ne -1\) 的位置是 \(j\)。现在相当于求在 \(x \times x\) 的左下角抠掉了 \(y \times y\) 的一块的“L”字形棋盘放 \(t\) 个互不攻击的车的方案数，其中 \(x = j - a_j, y = i - a_j, t = a_i - a_j\)。每个这样的“L”字形互相独立，所以可以直接把方案乘起来。
上面的问题可以考虑容斥（我现在还不会不容斥的做法？）。相当于在左下角 \(y \times y\) 的区域不能放车，那么我钦定 \(i\) 个车放在了左下角，设 \(F(n, m)\) 为 \(n \times n\) 的棋盘放 \(m\) 个互不攻击的车的方案数，那么这部分的方案为 \(F(x, i) \times F(y - i, t - i)\)，容斥系数为 \((-1)^i\)，因此结果为：
\[\sum\limits_{i = 0}^t (-1)^i F(x, i) F(y - i, t - i) \]最后一个问题是求 \(F(n, m)\)。考虑先选 \(m\) 行放车，有 \(\frac{n!}{(n - m)!}\) 种选列的方案，那么 \(F(n, m) = \binom{n}{m} \times \frac{n!}{(n - m)!}\)。
容易发现 \(\sum t = n\)，所以时间复杂度为 \(O(n)\)。
code
// Problem: F2. Small Permutation Problem (Hard Version)
// Contest: Codeforces - Pinely Round 3 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1909/problem/F2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, fac[maxn], a[maxn], ifac[maxn];
inline ll A(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[n - m] % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
inline ll F(ll n, ll m) {
return C(n, m) * A(n, m) % mod;
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
a[0] = 0;
if (a[n] != -1 && a[n] != n) {
puts("0");
return;
}
a[n] = n;
int j = 0;
ll ans = 1;
for (int i = 1; i <= n; ++i) {
if (a[i] != -1) {
int t = a[i] - a[j], x = j - a[j], y = i - a[j];
if (t < 0) {
puts("0");
return;
}
ll res = 0;
for (int i = 0; i <= x && i <= t; ++i) {
res = (res + ((i & 1) ? mod - 1 : 1) * F(x, i) % mod * F(y - i, t - i)) % mod;
}
ans = ans * res % mod;
j = i;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}