洛谷P3941入阵曲——二维k倍区间问题

k倍区间问题，貌似是2017年，蓝桥杯的一道题。传送门

在洛谷上遇到这道题的变式，有点惊喜，题面，其实就是将k倍区间拓展到二维罢了，怎么拓呢？我

们在解决k倍区间问题时，用了一个同余式的变形，利用前缀和解决这个问题：用prefix数组记录前缀和，

那么一个满足条件的区间就满足这个式子：( prefix[r] - prefix[l-1] ) % k == 0，这个式子等价于

prefix[ r ] % k == prefix[l - 1] % k，那么算法就很明显了，用一个num数组记录prefix[ i ] % k == j 的个数，假

如按i从小到大排，一共有5个前缀和mod k 余 j （j != 0），那么对于第一个 i ，它对答案没有贡献，但对

第二个 i 就有一个 i' 在它之前并和它同余，那么它对答案的贡献就是1， 对于第三个 i ，贡献为2， 第4个

贡献为3……那么代码，就顺理成章了，注意如果 j == 0 ，num[0]初始化为1。

在面对二维问题时，只需要解决一个问题就好啦：

如何枚举所有的矩形？

对于每一个矩形，都可以转化为横向上的两个矩阵前缀和的差（上下界一样）

那么枚举上下界和右边界或左右界和下界都可以，O(n^3)

记得初始化哦

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans = 0;
ll Mat[410][410];
ll prefix[410][410];
ll mod[410];
ll num[2000001];
ll n, m, k;
inline ll read()
{ll ch;ll x=0;ll f=1;ch=getchar();while (ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();ch=='-'?f=-1:x=ch-'0',ch=getchar();while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
signed main()
{n = read(); m = read(); k = read();for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){Mat[i][j] = read();prefix[i][j] = (prefix[i-1][j] + Mat[i][j] + prefix[i][j-1] - prefix[i-1][j-1]);(prefix[i][j] >= k) && (prefix[i][j] -= k);}for(int i = 0; i < n; i++)for(int j = i + 1; j <= n; j++){num[0] = 1;for(int p = 1; p <= m; p ++) {mod[p] = (prefix[j][p] - prefix[i][p] ) % k;(mod[p] < 0) && (mod[p] += k);ans += num[mod[p]]++;}for(int p = 1; p <= m; p ++) num[mod[p]] = 0;}printf("%lld\n", ans);return 0;
}