https://atcoder.jp/contests/abc410/tasks/abc410_fhttps://atcoder.jp/contests/abc410/tasks/abc410_f首先可以一眼看出暴力 ：枚舉左上角和右下角，用前綴和算出矩形中#的數量，判斷即可

但這樣是,爆!!!

考慮優化，我們可以枚舉矩形的兩條寬和一條長

我們將'#'看做1，'.'看做-1，題目就轉化成求矩形和為0的個數了

對于兩寬之間的區間,我們用前綴和+mp數組統計其區間中的矩形在不同值中出現的個數

由于矩陣之和為0，所以就是答案了（為長為1，寬為的矩形和）

(為了方便，代碼中改成)

最后將答案統計就可以了

多測清空+?

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,d[300010],mp[600010];
vector<int>a[300010];
vector<bool>b[300010];
signed main()
{scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&m);int ans=0;int Add=n*m;int kn=n,km=m;if(n>m) swap(kn,km);for(int i=0;i<=kn;i++){a[i].clear();b[i].clear();for(int j=0;j<=km;j++){a[i].push_back(0);b[i].push_back(0);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char ch;cin>>ch;if(ch=='#'){if(n<=m) b[i][j]=1;else b[j][i]=1;}}}if(n>m) swap(n,m);for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=a[i-1][j]+(b[i][j]?1:-1);d[0]=Add;for(int i=0;i<n;i++){for(int j=i+1;j<=n;j++){mp[Add]=1;for(int k=1;k<=m;k++){d[k]=d[k-1]+a[j][k]-a[i][k];ans+=mp[d[k]];mp[d[k]]++;}for(int k=0;k<=m;k++) mp[d[k]]=0;}}printf("%lld\n",ans);}return 0;
}