P3941 入阵曲

题目链接

二维前缀和直接枚举顶点统计答案。
可不可以不枚举呢？

如果两个前缀和在模\(k\)意义下相等，那这两个前缀和的子矩阵是\(k\)的倍数。
所以问题变成统计所有和相等的子矩阵对数。
可以枚举上下边，就可以统计所有以此为上下边的矩阵合法的对数。
注意要求的是单个矩阵是\(k\)的倍数，所以两个前缀和相减要是有意义的。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 405;
int n, m, k;
ll sum[N][N], b[1000005], ans, cnt[1000005];

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
        	scanf("%lld", &sum[i][j]);
            sum[i][j] = -sum[i - 1][j - 1] + sum[i][j - 1] + sum[i - 1][j] + sum[i][j];
            sum[i][j] = (sum[i][j] % k + k) % k;
        }
    for (int i = 0; i < n; i++)
    	for (int j = i + 1; j <= n; j++) {
    		cnt[0] = 1;
    		for (int l = 1; l <= m; l++) ans += cnt[b[l] = ((sum[j][l] - sum[i][l] + k) % k)]++;
    		for (int l = 1; l <= m; l++) cnt[b[l]] = 0;
    	}
    printf("%lld\n", ans);
    return 0;
}