#2203. Painting the perfect art

Painting the perfect art

Painting the perfect art

题目描述

标题: Painting the perfect art - Problem - QOJ.ac

#10228. Painting the perfect art

Statistics

The problem was used in the following contests:

Problem Statement

继杰克逊·波洛克和克利福德·斯蒂尔之后,亚当决定创作一些抽象艺术。他决定从简单的开始:画一幅由三颗星星组成的画。

亚当买了一张精致的纸,它可以被看作是一个由 n 行和 m 列组成的网格。亚当指定了一些适合画星星的格子。

由于这张纸很大,亚当需要先切出绘画所需的部分。它可以是网格的任何子矩形。形式化地,对于整数 x1,x2,y1,y2,如果 0≤x1≤x2<n 和 0≤y1≤y2<m,行编号在 [x1,x2] 且列编号在 [y1,y2] 的单元格构成一个子矩形。这些是全部的子矩形。然后,亚当需要在子矩形中找到三个不同的格子来绘制星星。当然,这些单元格应该被指定为适合画星星。

亚当想知道他有多少种方法来创造这样的艺术品。由于这个数字可能相当大,你只需要输出它对 109+7 取余的结果。

Implementation Details

你应该包含 art.h,并实现如下过程:

int count(bool[][] v)

  • v: 一个二维数组,大小为 n×m。对于每个 i,j(0≤i≤n−1, 0≤j≤m−1),v[i][j]=1 如果第 i 行第 j 列能画星星,否则 v[i][j]=0。
  • 你实现的过程会被调用恰好一次。
  • 你应该返回创造艺术品的方案数对 109+7 取余的值:一个 [0,109+6] 的整数。

Example

考虑如下调用:count([[1,1,0],[1,0,0]])

我们只能在其中的三个格子中画出星星,而且有两个不同的子矩形包含这三个星星。因此,有两种不同的创造艺术品的方法,一个正确的程序应该返回 2。

Constraints

1≤n,m≤3000

Subtasks

  1. (20 分)n,m≤80
  2. (20 分)n,m≤300
  3. (20 分)所有格子都可以画星星。
  4. (40 分)无特殊限制。

Sample Grader

样例交互器以下列格式读取输入。

  • 第一行:n m
  • 接下来 n 行每行 m 个 0 或 1 的字符,描述 v

样例交互器以下列格式打印你的输出。

  • 一行,你的返回值

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 3
110
100
2

样例 2

10 10
1001111001
0110110110
0110110110
1001101001
1111101111
1111001111
0111011110
0111111110
1011111101
1100000011
3398361