Submission #66745318

---

Source Code Expand

//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#include"atcoder/all"
using namespace atcoder;
typedef modint1000000007 mi;
using namespace std;
#define all(a) a.begin(),a.end()
#define compress(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
constexpr ll mod=998244353;
constexpr ll inf=3e18;

void solve(){
	int h,w;
	cin>>h>>w;
	vector<string>S;
	if(h<=w){
		S=vector<string>(h);
		rep(i,h)cin>>S[i];
	}
	else{
		vector<string>S2(h);
		S=vector<string>(w);
		rep(i,h){
			cin>>S2[i];
			rep(j,w)S[j].push_back(S2[i][j]);
		}
		swap(h,w);
	}
	vector<vector<int>>rs(h+1,vector<int>(w+1));
	rep(i,h){
		rep(j,w){
			if(S[i][j]=='#')rs[i+1][j+1]=1;
			else rs[i+1][j+1]=-1;
		}
	}

	rep(i,h+1){
		rep(j,w)rs[i][j+1]+=rs[i][j];
	}
	rep(i,h){
		rep(j,w+1){
			rs[i+1][j]+=rs[i][j];
		}
	}
	ll ans=0;


	vector<int>ss(w+1);
	unordered_map<int,ll>M;
	for(int i=0;i<=h;i++){
		for(int j=i+1;j<=h;j++){
			rep(k,w+1)ss[k]=rs[i][k]-rs[j][k];
			M.clear();
			rep(k,w+1){
				ans+=M[ss[k]];
				M[ss[k]]++;
			}
		}
	}
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t;
	cin>>t;
	rep(T,t)solve();
}

Submission Info

Judge Result