#PQJ1645x8353. QOJ 1645_8353

    ID: 2677 传统题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2022 集训前缀和递推

QOJ 1645_8353

标题: T1 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

小 T 有一个 n×m 的矩阵 A,A 中的元素互不相同,可以构成一个 1∼nm 的排列。

如果一个序列是升序或者降序的,则称这个序列是好的。如果一个矩阵的每一行是好的,每一列也是好的,则称这个矩阵是好的。

求有多少个 A 的非空子矩阵是好的。

一个矩阵的非空子矩阵是指,选出行的一个非空子集与列的一个非空子集,既在这些行又在这些列的元素排成的新矩阵。可以发现,一个 n×m 的矩阵的非空子矩阵数为 (2n−1)(2m−1)。

输入格式

第一行两个整数 n,m,表示矩阵大小。

接下来 n 行,每行 m 个整数 Ai,j,表示矩阵 A 的元素。

输出格式

一行一个整数表示答案。

样例输入 1

2 2
1 3
2 4

样例输出 1

9

样例输入 2

2 3
2 3 1
4 5 6

样例输出 2

19

样例输入 3

3 4
4 5 10 8
9 6 3 2
11 7 12 1

样例输出 3

79

样例解释

样例 1 中所有子矩阵均满足要求。

样例 2 中只有子矩阵为整个矩阵,或第一行的所有数时不满足要求。

数据范围

对于所有数据,1≤n,m≤20,1≤Ai,j≤nm,保证 Ai,j 互不相同。

子任务 1(20 分):n,m≤10。

子任务 2(25 分):n,m≤15。

子任务 3(25 分):n,m≤18。

子任务 4(30 分):无特殊限制。