P3400 Hamster Nest

The adorable "Created equal" is a little hamster, and of course a little hamster has a hamster nest. The nest is an $n\times m$ matrix with $n$ rows and $m$ columns. The little hamster wants to know how many submatrices this matrix has. For example, for a $2\times 3$ matrix, there are $6$ submatrices of size $1\times 1$, $4$ of size $1\times 2$, $2$ of size $1\times 3$, $3$ of size $2\times 1$, $2$ of size $2\times 2$, and $1$ of size $2\times 3$, so in total there are $6+4+2+3+2+1=18$ submatrices. However, some cells in the nest are damaged. Now the little hamster wants to know how many submatrices contain no damaged cells.

The first line contains two positive integers $n$ and $m$, denoting the number of rows $n$ and columns $m$ of the nest. Then follow $n$ lines, each containing $m$ numbers. Each number is either $0$ or $1$. A $0$ means the cell is damaged; otherwise the cell is intact.

Output a single integer: the number of submatrices that are undamaged.

The time limit is $2\text{s}$ and the memory limit is $256\text{M}$. Since the new judge is close in speed to the NOIP judge, please be mindful of the impact of constant factors. | Testdata index | $n$ | $m$ | Special property | | :----------------: | :---------: | :---------: | :----------------------: | | 1, 2, 3 | 2 | 2 | None | | 4 | 10 | 10 | None | | 5, 6 | 2000 | 2000 | All cells undamaged | | 7 | 2500 | 3000 | Exactly one cell broken | | 8 | 3000 | 2500 | Exactly one cell broken | | 9 | 200 | 200 | None | | 10, 11, 12 | 500 | 500 | None | | 13, 14 | 1000 | 1000 | None | | 15 | 1000 | 1500 | None | | 16 | 2500 | 2500 | None | | 17 | 2500 | 3000 | None | | 18 | 3000 | 2500 | None | | 19, 20 | 3000 | 3000 | None | Translated by ChatGPT 5