思路：枚举上下边界。先找到左右边框都是1的列，存在一个数组b里。
因为外边框要全是1，所以我们找到这个上下边界的连续的1的段，对每段都单独计算答案。
对每一段[l,r]而言，找到b数组的一个段，使得这些列都在[l,r]内。
然后我们枚举右边框，找有多少满足条件的左边框，这显然用一个数组记录一下前缀的矩形内部1，0差值就可以实现了。
时间复杂度
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int n,m;
int a[555][555];
int s[555][555];
int vis[510*510*2];
int main() {ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}}auto get=[&](int x,int y,int dx,int dy){return s[dx][dy]-s[dx][y-1]-s[x-1][dy]+s[x-1][y-1];};vis[n*m+1]=1;LL ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){vector<int>v;for(int k=1;k<=m;k++){if(get(i,k,j,k)==j-i+1){v.pb(k);}}if(!(int)v.size()){continue;}int sz=v.size();int dx=1,dy=1;int idx=0;while(dx<=m&&dy<=m){if(a[i][dx]==0||a[j][dy]==0){dx++;dy++;continue;}int ddx=dx;int ddy=dy;while(ddx+1<=m&&a[i][ddx+1]==1&&ddy+1<=m&&a[j][ddy+1]==1){ddx++;ddy++;}while(idx<sz&&v[idx]<dx)idx++;if(idx==sz) {break;}if(v[idx]>ddx) {dx=ddx+1;dy=ddy+1;continue;}int nx=idx;while(nx+1<sz&&v[nx+1]<=ddx)nx++;if(nx==idx) {idx++;dx=ddx+1;dy=ddy+1;continue;}for(int g=idx+1;g<=nx;g++){int now=v[g];int sum=get(i,v[idx],j,now);//矩形内的1 边框全是1int zero=(j-i+1)*(now-v[idx]+1)-sum;int diff=sum-zero-2*(j-i+1)-2*(now-v[idx]+1)+4;//矩形内 不包括边框的 1 0 diffans+=vis[n*m+1+diff]+vis[n*m+1+(diff-1)]+vis[n*m+1+(diff+1)];vis[n*m+1+diff+(j-i+1-2)]++;}for(int g=idx+1;g<=nx;g++){int now=v[g];int sum=get(i,v[idx],j,now);//矩形内的1 边框全是1int zero=(j-i+1)*(now-v[idx]+1)-sum;int diff=sum-zero-2*(j-i+1)-2*(now-v[idx]+1)+4;//矩形内 不包括边框的 1 0 diffvis[n*m+1+diff+(j-i+1-2)]--;}idx=nx+1;dx=ddx+1;dy=ddy+1;}}}cout<<ans<<'\n';return 0;
}