QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#10228. Painting the perfect art

Statistics

Problem Statement

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

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

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

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

Implementation Details

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

int count(bool[][] v)

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

Example

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

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

Constraints

$1\le n,m\le 3000$

Subtasks

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

Sample Grader

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

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

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

  • 一行,你的返回值

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.