题解 - ARC118E Avoid Permutations
hopeful_imitation
·
·
题解
题解 - ARC118E Avoid Permutations
不太会容斥原理，选择一个和组合数学基本没啥关系的直接 DP 方法。
简述题意
定义排列 a 权值为：在 (n+2)\times(n+2) 网格图上删掉所有点 (i,a_i)，每步只能从 (i,j) 走到 (i+1,j) 或 (i,j+1)，从 (0,0) 走到 (n+1,n+1) 的方案数。现在把 a 的若干位隐藏为 -1，求所有可能的 a 的权值和。n\le 200。
分析
首先假设完全观察不到容斥，才来暴力刻画 DP 状态。
考虑以路径为主体，只关心这个路径要走到的下一个点有没有被删掉。而每行、每列（除了 0 和 n+1）都恰好有一个点被删掉。
假设当前路径已经走到 (x,y)，那么我们只考虑子矩形 [0,x]\times[0,y] 的总和。每当路径走到 (x,y+1) 或 (x+1,y)，都相当于是扩充了一行或一列，这扩充的部分可能有一个被删掉的点，也可能没有。这个删掉的点可能是某个 -1 的决策，也可能是某个既定的决策。但是走到的那个点不可以被删掉，删掉的那个点要么在它下面，要么在它上面（或要么在它左边，要么在它右边）。基于这样的想法，我们设计状态来刻画。
考虑顺推转移。初始状态是 $f_{0,0,0,0,0}=1$。
对于向上的转移，如果新的一行删掉的点不在左边，需要满足以下之一：
- $x=n+1$。
- 假设 $b$ 为 $a$ 的逆排列（未出现设为 $-1$），$b_{y+1}>x$。
- $b_{y+1}=-1$。
转移系数为 $1$。
如果新的一行删掉的点在左边：
- 如果有一个既定的点在右边，或者当前在第 $n+1$ 行，不可以转移；
- 如果有一个既定的点在左边，那直接转移；
- 否则要考虑这个系数，就是在 $(x,y)$ 的左边选择一个 $-1$ 填这个值，是 $c-1$ 或 $c$（因为第 $x$ 列自己可能被计入 $c$）。
对于向右的转移，如果新的一列删掉的点不在下面，也是要满足三个条件之一，和上面向上转移不考虑删数的对称。
如果在下面，那么这一位如果有既定的决策也是直接以 $0$ 或 $1$ 为转移系数。否则，就要计算 $(x,y)$ 下方有多少个还未被填的值，这个可以推出。具体来说，令 $\textrm{nc}_i$ 表示有多少个 $j<i$ 满足 $a_j=-1$，令 $\textrm{hc}_i$ 表示有多少个 $j<i$ 满足 $j$ 不存在于输入的 $a$，那么这个系数就是 $\textrm{hc}_y-(\textrm{nc}_i-c)$，视情况加一（因为第 $y$ 行左侧可能有已经确定的 $-1$ 未被去除影响）。
写转移的时候还要留意一下 $c$ 的变化。
最终答案就是 $f_{n+1,n+1,0,0,0}$。
## 代码
细节真的不少。如果会容斥原理还是不要不切实际地写这种东西。
```cpp
const int MXN = 205;
const int DVS = 998244353;
int N, nc[MXN], hc[MXN], arr[MXN], rev[MXN], cnt[MXN][MXN][MXN][2][2];
inline void add(int& x, int y) {
if ((x += y) >= DVS) x -= DVS;
}
int main() {
cin >> N;
memset(arr, -1, sizeof arr);
memset(rev, -1, sizeof rev);
for (int i(1); i <= N; ++i)
cin >> arr[i], rev[arr[i]] = i;
for (int i(2); i <= N + 1; ++i)
nc[i] = nc[i - 1] + (arr[i - 1] == -1),
hc[i] = hc[i - 1] + (rev[i - 1] == -1);
cnt[0][0][0][0][0] = 1;
for (int x(0); x <= N + 1; ++x) {
for (int y(0); y <= N + 1; ++y) {
for (int c(0); c <= x; ++c) {
for (int a(0); a <= 1; ++a) {
for (int b(0); b <= 1; ++b) {
if (!cnt[x][y][c][a][b]) continue;
if (x + 1 <= N + 1) {
int coe(0);
if (x + 1 == N + 1 || arr[x + 1] >= y) coe = 0;
else if (~arr[x + 1] && arr[x + 1] < y) coe = 1;
else
coe = max(0, hc[y] - (nc[x + 1] - c - (a && rev[y] == -1)));
add(cnt[x + 1][y][c][a][1],
cnt[x][y][c][a][b] * 1LL * coe % DVS);
if (x + 1 == N + 1 || arr[x + 1] > y || arr[x + 1] == -1)
add(cnt[x + 1][y][c + (x != N && arr[x + 1] == -1)][a][0],
cnt[x][y][c][a][b]);
}
if (y + 1 <= N + 1) {
int coe(0);
if (y + 1 == N + 1 || rev[y + 1] >= x) coe = 0;
else if (~rev[y + 1] && rev[y + 1] < x) coe = 1;
else coe = max(0, c - (!b && arr[x] == -1 && x != N + 1));
add(cnt[x][y + 1][c - (rev[y + 1] == -1)][1][b],
cnt[x][y][c][a][b] * 1LL * coe % DVS);
if (y + 1 == N + 1 || rev[y + 1] > x || rev[y + 1] == -1)
add(cnt[x][y + 1][c][0][b],
cnt[x][y][c][a][b]);
}
}
}
}
}
}
cout << cnt[N + 1][N + 1][0][0][0] << endl;
return 0;
}
```