NC53676 「土」秘法地震（二维前缀和）

题意

帕秋莉掌握了一种土属性魔法

这种魔法可以在一片k×k大小的一个正方形区域内产生地震

但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法

整个地图大小为n×m，其中一些地方有建筑

请问有多少种可能的情况，使得帕秋莉会停止施法

地图用 矩阵表示， 表示有建筑， 表示没有。

其中，, 。

分析

枚举正方形的左上顶点，那么正方形区域为 。
现在问题就是判断一个矩形区域中是否有建筑物，这个可以用二维前缀和快速判断。
记 。
根据容斥原理：。
假设要求的区域为 。
那么继续根据容斥原理，整块的和为：。
最终复杂度是

代码如下

#include <bits/stdc++.h>
using namespace std;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int s[1005][1005];
int main(){
    int i, j, n, m, k, c, x, y, ans = 0;
    n = read(); m = read(); k = read();
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            scanf("%1d", &s[i][j]);
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            if(i + k - 1 > n || j + k - 1 > m) break;
            x = i + k - 1, y = j + k - 1;
            if(s[x][y] - s[i - 1][y] - s[x][j - 1] + s[i - 1][j - 1]) ans++;
        }
    }
    printf("%d", ans);
    return 0;
}