ARC118E 题解

EuphoricStar · 2023-03-13 15:08:23 · 题解

提供一种形式化的理解方法。

设 S 为任意一条从 (0,0) 到 (n+1,n+1) 的路径经过的点集，P 为 所有 合法障碍点集，Q 为 题目给定的 障碍点集。显然现在 S 和 P 都不确定，题目即求 \sum\limits_S \sum\limits_P [S \cap P = \varnothing]。

注意到可以容斥，即 ans = \sum\limits_S \sum\limits_P \sum\limits_{P' \subseteq S \cap P} (-1)^{|P'|}。

调换枚举顺序，得 ans = \sum\limits_{S} \sum\limits_{P' \subseteq S} (-1)^{|P'|} \sum\limits_{P' \subseteq P}1。

考虑若确定了 P'，最后有 n - |P' \cup Q| 行和列是自由的，因此 P 的方案数为 (n - |P' \cup Q|)!，即 ans = \sum\limits_S \sum\limits_{P' \subseteq S} (-1)^{|P'|}(n - |P' \cup Q|)!。

此时考虑 dp，并把 (-1)^{|P'|} 塞入转移中。设 f_{i,j,k,p=0/1,q=0/1} 表示当前走到 (i,j)，|P' \cup Q|=k，第 i 行是否 \exists x,x \in P'，第 j 列是否 \exists x,x \in P'。

转移枚举下一次走 (i+1,j) 还是 (i,j+1)，以及这个点是否加入 P'，即：

初值为 f_{0,0,|Q|,0,0} = 1。

最后 ans = \sum\limits_{i=0}^n (n-i)! \times f_{n+1,n+1,i,0,0}。

时间复杂度 O(n^3)。

code