题面

题意

问满足下列条件的 $n \times m$ 的 01 矩阵 $a$ 的数量：

1. $\exists [l,~r] (1 \le l \le r \le n)$，满足 $\forall i \in [l,~r],~\sum_j a_{i,j} =2$ 且 $\forall i \notin [l,~r],~\sum_j a_{i,j}=0$。
2. 设 $[l,~r]$ 中的每一行的第一个值为 $1$ 的位置的下标为 $x_i$，第二个值为 $1$ 的位置的下标为 $y_i$，则：$\exists t \in [l,~r]$，满足 $\forall i \in [l,~t-1],~x_i \ge x_{i+1},~y_i \le y_{i+1}$ 且 $\forall i \in [t,~r-1],~x_i \le x_{i+1},~y_i \ge y_{i+1}$。

分析

考虑使用 DP 解决本题。

令 $f[i][j]$ 表示考虑洞的前 $i$ 行（该 $i$ 行都在洞的中间位置 $t$ 的上方）且第 $i$ 行的 $y_i-x_i+1=j$ 时该洞的构造方案（不考虑洞在矩阵中的摆放位置）。

考虑枚举第 $i-1$ 行的长度以及与第 $i$ 行的相对位置，得出转移方程：

$$
f[i][j]=\sum_{t=0}^{j}f[i-1][t] \times (j-t+1)
$$

尝试使用该数据描述最终答案 $Ans$，考虑枚举中间位置 $t$ 的行编号以及该行 $y_i-x_i+1$ 的大小。同时由于可能存在构造洞的方案满足第 $t$ 行与相邻的几行的形态完全相同，为了防止算重，考虑令 $t$ 为洞的最大的满足 $y_i-x_i+1$ 最大的行数，同时枚举 $t+1$ 行的长度（小于 $t$ 行长度），算出最终答案：

$$
\begin{aligned}
Ans&=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{l=1}^{i} f[i-l+1][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{r=i+1}^{n} f[r-i][b] \big) \times (a - b + 1))\\
&=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{t=1}^{i} f[t][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{t=1}^{n-i} f[t][b] \big) \times (a - b + 1))
\end{aligned}
$$

令 $g[i][j] = \sum_{k=1}^{i} f[k][j]$。

$$
Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + \sum_{b=0}^{a-1} g[n-i][b] \times (a-b+1))
$$

令 $h[i][j]=\sum_{k=0}^{j-1} g[i][k] \times (j-k+1)$。

$$
Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + h[n-i][a])
$$

处理 $f[i][j]$ 前缀和优化到 $O(nm)$，处理 $g[i][j]$ $O(nm)$，处理 $h[i][j]$ 前缀和优化到 $O(nm)$，计算答案 $Ans$ $O(nm)$。

总时间复杂度 $O(nm)$。

代码

View on Github