2092: [蓝桥杯2023初赛] 子矩阵

内存限制:256 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:150 通过:27

题目描述

给定一个 n × m (n 行 m 列)的矩阵。
设一个矩阵的价值为其所有数中的最大值和最小值的乘积。
求给定矩阵的所有大小为 a × b (a 行 b 列)的子矩阵的价值的和。
答案可能很大,你只需要输出答案对 998244353 取模后的结果。

输入格式

输入的第一行包含四个整数分别表示 n, m, a, b,相邻整数之间使用一个空格分隔。
接下来 n 行每行包含 m 个整数,相邻整数之间使用一个空格分隔,表示矩阵中的每个数Aij
对于 40% 的评测用例,1 ≤ n,m ≤ 100 ;
对于 70% 的评测用例,1 ≤ n,m ≤ 500 ;
对于 100% 的评测用例,1 ≤ a ≤ n ≤ 1000, 1 ≤ b ≤ m ≤ 1000, 1 ≤ Aij ≤ 109

输出格式

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

输入样例 复制

2 3 1 2
1 2 3
4 5 6

输出样例 复制

58

数据范围与提示

1 × 2 + 2 × 3 + 4 × 5 + 5 × 6 = 58 。