仓鼠窝
题目描述
萌萌哒的 Created equal 是一只小仓鼠,小仓鼠自然有仓鼠窝啦。
仓鼠窝是一个由 $n\times m$ 个格子组成的行数为 $n$、列数为 $m$ 的矩阵。小仓鼠现在想要知道,这个矩阵中有多少个子矩阵。
比如说有一个 $2\times 3$ 的矩阵,那么 $1\times 1$ 的子矩阵有 $6$ 个,$1\times 2$ 的子矩阵有 $4$ 个,$1\times 3$ 的子矩阵有 $2$ 个,$2\times 1$ 的子矩阵有 $3$ 个,$2\times 2$ 的子矩阵有 $2$ 个,$2\times 3$ 的子矩阵有 $1$ 个,所以子矩阵共有 $6+4+2+3+2+1=18$ 个。
可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道,有多少个内部不含被破坏的格子的子矩阵。
输入输出格式
输入格式
第一行两个正整数 $n$ 和 $m$,分别表示仓鼠窝的行数 $n$,列数 $m$。
接下来 $n$ 行,每行 $m$ 个数,每个数代表对应的格子,非 $0$ 即 $1$。若为 $0$,表示这个格子被破坏;反之代表这个格子是完好无损的。
输出格式
仅一个正整数,表示未被破坏的子矩阵的个数。
输入输出样例
输入样例 #1
3 4
1 1 1 1
1 0 1 1
1 1 0 1
输出样例 #1
26
说明
本题时限 $2\text{s}$,内存限制 $256\text{M}$,因新评测机速度较为接近 NOIP 评测机速度,请注意常数问题带来的影响。
| 数据编号 | $n$ | $m$ | 特殊性质 |
| :------------: | :-----------: | :----------: | :--------------------: |
| $1, 2, 3$ | $2$ | $2$ | 无 |
| $4$ | $10$ | $10$ | 无 |
| $5, 6$ | $2000$ | $2000$ | 所有格子均未被破坏 |
| $7$ | $2500$ | $3000$ | 有且仅有一个格子被破坏 |
| $8$ | $3000$ | $2500$ | 有且仅有一个格子被破坏 |
| $9$ | $200$ | $200$ | 无 |
| $10, 11, 12$ | $500$ | $500$ | 无 |
| $13, 14$ | $1000$ | $1000$ | 无 |
| $15$ | $1000$ | $1500$ | 无 |
| $16$ | $2500$ | $2500$ | 无 |
| $17$ | $2500$ | $3000$ | 无 |
| $18$ | $3000$ | $2500$ | 无 |
| $19, 20$ | $3000$ | $3000$ | 无 |