题面
话说题目前面的那首诗还挺有意境的啊哈哈.
可能今天要把中文的标点都换成英文的了, 先熟悉一下吧...
好了, 进入正题, 求一个矩阵内有多少个子矩阵满足这个子矩阵的和模k为零.看到矩阵和啊, 第一感觉就是前缀和数组,在这里便是二维前缀和, 有这样一个算式:
[sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]
]
这个算式是怎样推出来的呢, 请大家自行画图解决, 应该是很好理解的.
二维前缀和算出来了之后, 我们可以枚举x1, x2, y1, y2, 不妨令x1 <= x2, y1 <= y2, 则有这样一个算式, 矩阵和为:
[sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]
]
这样的时间复杂度为:
[O(n ^ 2m^2)
]
这肯定会爆, 考虑优化, 首先, 前缀和还是要留着的, 那我们需要怎么做呢, 思考5S...
好了, 考虑压行, 我们知道两个模k同余的数相减模k必为0, 所以我们可以枚举子矩阵的上下两行或者左右两列, 在这里以上下两行为列, 从左往右枚举列, 将模k同余的数放进一个数组中保存, 每次新列加上与他同余的数的个数就是上下两行为枚举的i, j, 右边一列为枚举的k的子矩阵模k为零的个数, 好了, 具体实现在注释中会提到.
现在的时间复杂度已经被优化到了:
[O(n ^ 2m)
]
代码实现
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, K, mapp[405][405], cnt[1000005], b[405];
long long ans; //对于答案需要统计的问题, 开成longlong比较保险
inline int read()
{
int x = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * w;
}
int main()
{
// freopen("rally.in", "r", stdin);
// freopen("rally.out", "w", stdout);
n = read(); m = read(); K = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
mapp[i][j] = read();
(mapp[i][j] += mapp[i - 1][j] + mapp[i][j - 1] + K - mapp[i - 1][j - 1]) %= K;
}
for(int i = 0; i < n; i++)
for(int j = i + 1; j <= n; j++)
{
cnt[0] = 1;//模k为0的子矩阵初始有1个, 如果第k个矩阵本身模k就为零了,减去一个空的事实上不存在的矩阵不还是等于零吗, 因为有一个前缀和, 事实上是sum[r] - sum[l - 1]嘛, 不就相当于sum[-1] % k == 0
for(int k = 1; k <= m; k++) ans += cnt[(b[k] = (mapp[j][k] - mapp[i][k] + K)) %= K]++; //b[k]统计的是第k列为右边界,第0列为左边界的子矩阵模k的值, 这样清零就只有O(m)了, 不然由于模数比较大, memset肯定会超时, 这里需要注意一下, 还有, 这个地方的写法比较玄学, 其实可以写成以下形式:
/*
for(int k = 1; k <= m; k++)
{
b[k] = (mapp[j][k] - mapp[i][k] + K) % K;
ans += cnt[b[k]];
cnt[b[k]]++;
}
*/
for(int k = 1; k <= m; k++) cnt[b[k]] = 0;
}
printf("%lld
", ans);
return 0;
}