时间限制： 0.5 秒

空间限制： 256 MB

题目描述

A 国和 B 国正在激烈交战中，A 国的指挥官来到位于作战前的一块矩形区域，并且想要在这块土地埋下 A 国特制的地雷阵列。矩形地域的长和宽分别为 $n$ 和 $m$，而作为指挥官手下的你将会得到这块这块土地的简易地图，一个 $m$ 行 $n$ 列的 $01$ 矩阵。其中同一行从左到右的方向表示矩形的长度，同一列从上到下的方向表示矩形的宽度。在地图上，$0$ 表示这个位置上有障碍物，无法填埋地雷；$1$ 表示这个位置是空地，可以填埋地雷。

已知 A 国的地雷阵列只能在空地上填埋成矩阵的形状。此外，阵列的长必须大于等于 $1$ 且小于等于 $L$，宽必须大于等于 $1$ 且小于等于 $W$。为了控制成本，指挥官只想埋下一个地雷阵列。指挥官想请你算出一共有多少种填埋地雷的方案。若两个方案中地雷阵列的大小或位置不同，这两种方案便被认为是不同的。

由于总方案数可能很大，所以只要向指挥官报告方案数模 $10007$ 的结果即可。

输入格式

从标准输入读入数据。

第一行包含两个正整数 $n$ 和 $m$，表示矩形地域的长和宽。

第二行包含两个整数 $L$ 和 $W$，表示地雷阵列的最大长度和宽度。

接下来 $m$ 行，每行有 $n$ 个为 $0$ 或 $1$ 的整数，表示土地的简易地图。

输出格式

输出到标准输出。

一行一个整数，表示总方案数对 $10007$ 取模的结果。

3 3
2 2
0 1 1
1 0 1
1 0 1

10

样例 1 解释

我们以 $l\times w$ 表示长为 $l$ 宽为 $w$ 的矩阵，则：

• $1\times 1$ 的地雷阵列有 $6$ 种；
• $1\times 2$ 的地雷阵列有 $3$ 种；
• $2\times 1$ 的地雷阵列有 $1$ 种；
• $2\times 2$ 的地雷阵列不存在。

因此总方案数为 $6+3+1=10$。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（20 分）：$n,m\le 10$；
• 子任务 2（30 分）：$n,m\le 300$；
• 子任务 3（50 分）：无特殊限制。

对于所有数据，保证 $1\le L\le n\le 2000,~1\le W\le m\le 2000$。

本题输入量较大，请采用效率较高的读入方式。

提示

Chap 04 栈 直方图内最大矩形

1. 如果不会的话，建议先做一下 [CSP201312] 最大的矩形一题。
2. 从直方图最大矩形到 $01$ 矩阵的内极大 or 最大矩形的建模转换，可以做一下 AcWing 152. 城市游戏一题，推荐查看这篇建模转换非常形象的题解。
3. 本题当中我们可以类似求出给定长边下的所有极大子矩形（注意不重不漏）。对于一个 $l\times w$ 的全 $1$ 极大子矩阵，小于等于其规模的子矩阵个数，可以在记录个数的数组中分别以长递减和宽递减的方向各做一次二阶前缀和得到。
4. 如何利用差分和前缀和的性质，不重不漏地计算所有种类的全 $1$ 子矩阵个数，将是解决本题的关键。

来源

DSA OJ 编程作业