题解：AT_abc461_d [ABC461D] Count Subgrid Sum = K

int4399 · 2026-06-07 07:52:00 · 题解

题意：求有多少子矩阵的和为 k，n\le 500。

暴力显然是 O(n^4) 的，考虑怎么优化。我们考虑固定竖着的上下边界，即两根竖线。那么就转化成找两根横线，使得他们卡成的矩形和为 k，那么我们考虑前缀和压维，设 pre_i 表示当前情况下第一根横线在最上方，另一根横线在第 i 行的矩阵和，那么两根线能拼成答案的条件就是 pre_i-pre_j=k，我们开个桶即可，复杂度 O(n^3)。

#include<bits/stdc++.h>
using namespace std;
int h,w,k,pre[505][505];
long long ans;
char mp[505][505];
int main(){
    cin>>h>>w>>k;
    for(int i=1;i<=h;i++)for(int j=1;j<=w;j++) cin>>mp[i][j];
    for(int i=1;i<=w;i++)for(int j=1;j<=h;j++) pre[i][j]=pre[i][j-1]+mp[j][i]-'0';
    for(int i=1;i<=h;i++)for(int j=i;j<=h;j++){
        unordered_map<int,int> cnt;
        cnt[0]=1;int p=0;
        for(int c=1;c<=w;c++){
                int val=pre[c][j]-pre[c][i-1];
                p+=val;int target=p-k;
                auto it=cnt.find(target);
                if(it!=cnt.end()) ans+=it->second;
                ++cnt[p];
            }
    }
    return cout<<ans,0;
}