题解 - 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_{x,y,c,a,b}(a,b\in \{0,1\})$ 意为路径走到了 $(x,y)$，所有合法的状态数。状态是路径和填数方案的总和，填数方案要满足：在子矩形 $[0,x]\times[0,y]$ 中，有 $c$ 个 $-1$ 满足 $a_i>y$，$a$ 指示 $(x,y)$ 左边是否有点被删掉，$b$ 指示下边。

考虑顺推转移。初始状态是 $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}$。

代码

细节真的不少。如果会容斥原理还是不要不切实际地写这种东西。

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;
}