题意
给定一个长度为 \(n\) 的排列 \(p\)，在一个 \((n + 2)\times(n + 2)\) 的网格上，禁止通过 \((i, p_i)\) 这些点，每次只能向上或右走一格，从 \((0, 0)\) 走到 \((n + 1, n + 1)\) 的方案数，定义为排列的权值。给定一个不完整的排列，对于所有补全排列的方案，计算权值和。
数据范围：\(1\le n \le 200\)。
做法
这题并不需要容斥。
考虑计算对于某一条路径，有多少排列满足没有点在路径上。那么正常 DP 路径，在 \((i, j)\) 这个点向上转移到 \((i, j + 1)\) 的时候决策 \(y = j + 1\) 这一行左侧是否放置一个物品、放置在哪个位置，同时记录当前位置左下角区域总共放置了多少障碍。DP 状态设计为 \(f_{i, j, k, 0/1, 0/1}\) 表示在 \((i, j)\) 左下角放了 \(k\) 个障碍，这一行左边是不是已经放了东西，这一列下面是不是已经放了东西。转移需要一些讨论。时间复杂度 \(\Theta(n^3)\)。
代码
// Author: kyEEcccccc
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)
const int N = 205, MOD = 998244353;
int n, p[N], q[N];
int toti[N], totj[N];
LL f[N][N][N][2][2];
signed main(void)
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(nullptr);
cin >> n;
F(i, 1, n)
{
cin >> p[i];
if (p[i] != -1) q[p[i]] = i;
}
F(i, 1, n)
{
toti[i] = toti[i - 1];
totj[i] = totj[i - 1];
if (p[i] <= 0) toti[i] += 1;
if (q[i] <= 0) totj[i] += 1;
}
toti[n + 1] = toti[n];
totj[n + 1] = totj[n];
F(i, 0, n + 1) f[i][0][0][0][0] = f[0][i][0][0][0] = 1;
F(i, 1, n + 1) F(j, 1, n + 1) F(k, 0, min(toti[i], totj[j])) F(a, 0, 1) F(b, 0, 1)
{
LL &res = f[i][j][k][a][b];
if (((a == 1 && p[i] <= 0) || (b == 1 && q[j] <= 0)) && k == 0) continue;
if ((i == n + 1 && a == 1) || (j == n + 1 && b == 1)) continue;
if (p[i] > 0 && p[i] == j) continue;
if (p[i] > 0 && ((p[i] < j && a == 0) || (p[i] > j && a == 1))) continue;
if (q[j] > 0 && ((q[j] < i && b == 0) || (q[j] > i && b == 1))) continue;
if (a == 0)
{
res = (res + f[i - 1][j][k][0][b] + f[i - 1][j][k][1][b]) % MOD;
}
else
{
if (p[i] > 0)
{
res = (res + f[i - 1][j][k][0][b] + f[i - 1][j][k][1][b]) % MOD;
}
else if (q[j] <= 0)
{
res = (res + (f[i - 1][j][k - 1][0][b] + f[i - 1][j][k - 1][1][b])
* (totj[j - 1] - k + 1 + b)) % MOD;
}
else
{
res = (res + (f[i - 1][j][k - 1][0][b] + f[i - 1][j][k - 1][1][b])
* (totj[j - 1] - k + 1)) % MOD;
}
}
if (b == 0)
{
res = (res + f[i][j - 1][k][a][0] + f[i][j - 1][k][a][1]) % MOD;
}
else
{
if (q[j] > 0)
{
res = (res + f[i][j - 1][k][a][0] + f[i][j - 1][k][a][1]) % MOD;
}
else if (p[i] <= 0)
{
res = (res + (f[i][j - 1][k - 1][a][0] + f[i][j - 1][k - 1][a][1])
* (toti[i - 1] - k + 1 + a)) % MOD;
}
else
{
res = (res + (f[i][j - 1][k - 1][a][0] + f[i][j - 1][k - 1][a][1])
* (toti[i - 1] - k + 1)) % MOD;
}
}
}
cout << f[n + 1][n + 1][toti[n]][0][0] << endl;
return 0;
}