3514. 五彩地砖

单点时限: 1.5 sec

内存限制: 256 MB

易欧杰魔法学校的大厅里铺设了五颜六色的地砖,你可以将大厅视为一个 $n \times m$ 的矩阵,$a_{i,j}$ 代表第 $i$ 行第 $j$ 列的颜色,一共有 $c$ 种颜色,你现在需要知道有多少子矩阵是五彩矩阵。

五彩矩阵的定义如下:

  1. 五彩矩阵是 $n \times m$ 矩阵的子矩阵
  2. 矩阵的每一行,每一列都是由连续的颜色组成的。具体地说,对于 $a_{i,j}$,若 $a_{i+1,j}$ 存在,则 $a_{i+1,j}-a_{i,j} \equiv \pm 1 \pmod c$,且若 $a_{i-1,j}$ 与 $a_{i+1,j}$ 同时存在,则必须满足 $a_{i-1,j} - a_{i,j} \equiv a_{i,j} - a_{i+1,j} \pmod c$,对于列同样如此。

输入格式

第 $1$ 行包含两个整数 $n$,$m$,$c$。($1 \leq n, m, c \leq 1~000$)
第 $1+i$ 行包含 $m$ 个整数,表示 $a_{i,1}, a_{i, 2}, \ldots a_{i, m}$($1 \leq a_{i,j} \leq c$)

输出格式

输出一行一个整数,表示五彩矩阵的数量。

样例

Input
3 3 3
1 2 3
2 2 2
3 2 1
Output
21

3 人解决,5 人已尝试。

3 份提交通过,共有 39 份提交。

8.6 EMB 奖励。

创建: 4 年,3 月前.

修改: 4 年,3 月前.

最后提交: 1 年,7 月前.

来源: EOJ Monthly 2018.3

题目标签