题面

题意

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

1. $\mathrm{\exists }[l,r](1\le l\le r\le n)$，满足 $\mathrm{\forall }i\in [l,r],\sum _j{a}_{i,j}=2$ 且 $\mathrm{\forall }i\notin [l,r],\sum _j{a}_{i,j}=0$。
2. 设 $[l,r]$ 中的每一行的第一个值为 $1$ 的位置的下标为 $x_i$，第二个值为 $1$ 的位置的下标为 $y_i$，则：$\mathrm{\exists }t\in [l,r]$，满足 $\mathrm{\forall }i\in [l,t-1],x_i\ge x_{i+1},y_i\le y_{i+1}$ 且 $\mathrm{\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{array}{rl}Ans& =\sum _{i=1}^n\sum _{a=0}^{m-2}(m-a-1)\times (\sum _{l=1}^{i}f[i-l+1][a])\times (1+\sum _{b=0}^{a-1}(\sum _{r=i+1}^{n}f[r-i][b])\times (a-b+1))\\ & =\sum _{i=1}^n\sum _{a=0}^{m-2}(m-a-1)\times (\sum _{t=1}^{i}f[t][a])\times (1+\sum _{b=0}^{a-1}(\sum _{t=1}^{n-i}f[t][b])\times (a-b+1))\end{array}$$

令 $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