洛谷P3941 - 入阵曲 - 二维版k倍区间

链接：

https://www.luogu.org/problemnew/show/P3942

题目：

题目描述

丹青千秋酿，一醉解愁肠。
无悔少年枉，只愿壮志狂。小F很喜欢数学，但是到了高中以后数学总是考不好。有一天，他在数学课上发起了呆；他想起了过去的一年。一年前，当他初识算法竞赛的时候，觉得整个世界都焕然一新。这世界上怎么会有这么多奇妙的东西？曾经自己觉得难以解决的问题，被一个又一个算法轻松解决。小F当时暗自觉得，与自己的幼稚相比起来，还有好多要学习的呢。一年过去了，想想都还有点恍惚。他至今还能记得，某天晚上听着入阵曲，激动地睡不着觉，写题写到鸡鸣时分都兴奋不已。也许，这就是热血吧。

也就是在那个时候，小F学会了矩阵乘法。让两个矩阵乘几次就能算出斐波那契数列的第10100项，真是奇妙无比呢。不过，小F现在可不想手算矩阵乘法——他觉得好麻烦。取而代之的，是一个简单的小问题。他写写画画，画出了一个n×m的矩阵，每个格子里都有一个不超过k的正整数。
小F想问问你，这个矩阵里有多少个不同的子矩形中的数字之和是k的倍数？如果把一个子矩形用它的左上角和右下角描述为(x1,y1,x2,y2)，其中x1≤x2,y1≤y2；
那么，我们认为两个子矩形是不同的，当且仅当他们以(x1,y1,x2,y2)表示时不同；也就是说，只要两个矩形以(x1,y1,x2,y2)表示时相同，就认为这两个矩形是同一个矩形，你应该在你的答案里只算一次。

输入

输入第一行，包含三个正整数n,m,k。输入接下来n行，每行包含m个正整数，第

输出

输入一行一个非负整数，表示你的答案。

样例输入

2 3 2
1 2 1
2 1 2

样例输出

6

提示

这些矩形是符合要求的：(1,1,1,3)，(1,1,2,2)，(1,2,1,2)，(1,2,2,3)，(2,1,2,1)，(2,3,2,3)。

思路：

  k倍区间的二维版，i、j枚举子矩阵的上下边界，k枚举处理到了第几列，把i、j行之间，右边界是第k列的这个矩阵和取模统计一下，具体原理在链接里说的很详细，$O(n^3)$可过。

实现：

#include <cstdio>
typedef long long ll;
const int maxn = 507;
ll ans = 0;
int cnt[int(1e6) + 7], num[maxn], sum[maxn][maxn];
int main() {int n, m, k, tmp;scanf("%d%d%d", &n, &m, &k);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%d", &tmp);sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + tmp - sum[i - 1][j - 1];if (sum[i][j] >= k) sum[i][j] -= k;}}for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {cnt[0] = 1;for (int cur = 1; cur <= m; cur++) {num[cur] = (sum[j][cur] - sum[i - 1][cur]) % k;if (num[cur] < 0) num[cur] += k;ans += cnt[num[cur]];cnt[num[cur]]++;}for (int cur = 1; cur <= m; cur++) cnt[num[cur]] = 0;}}printf("%lld\n", ans);return 0;
}