#P9623. 矩阵学说

    ID: 6240 传统题 4000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高网格 DP快速选择滚动数组

矩阵学说

题目描述

给定一个 n×mn\times m 矩阵 aa,矩阵的第 ii 行第 jj 列为 ai,ja_{i,j},求满足以下条件的三元组 (i,j,k)(i,j,k) 数量:

  • 1≤i≤n1\le i \le n,1≤j≤m1 \le j \le m,1≤x≤min⁡(n−i+1,m−j+1)1 \le x \le \min(n-i+1,m-j+1)
  • 以 (i,j)(i, j) 为左上角,(i+x−1,j+x−1)(i + x − 1, j + x − 1) 为右下角的子矩形恰好包含k个不同的整数。

输入格式

第一行三个整数 nn,mm,kk。

接下来 nn 行每行 mm个整数,第 i+1i+1 行第 jj 个整数为 ai,ja_{i,j}。

输出格式

输出一行一个整数表示答案。

样例

样例 1

2 3 4
1 2 3
4 5 6
2

数据范围

测试点 数据约束
1∼41\sim 4 n,m≤10n,m \le 10
5∼85 \sim 8 n,m≤50n,m\le 50
9∼169 \sim 16 n,m≤500n,m \le 500
17∼4017 \sim 40 无特殊性质

对于全部数据:1≤n,m≤15001 \le n,m \le 1500,1≤ai,j≤1001\le a_{i,j}\le 100,1≤k≤n×m1\le k \le n\times m。