#PQJ1940x10228. QOJ 1940_10228
QOJ 1940_10228
标题: Painting the perfect art - Problem - QOJ.ac
#10228. Painting the perfect art
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
- (20 分)n,m≤80
- (20 分)n,m≤300
- (20 分)所有格子都可以画星星。
- (40 分)无特殊限制。
Sample Grader
样例交互器以下列格式读取输入。
- 第一行:n m
- 接下来 n 行每行 m 个 0 或 1 的字符,描述 v
样例交互器以下列格式打印你的输出。
- 一行,你的返回值