Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #include <bits/stdc++.h>
- using namespace std;
- #define rep(i,a,n) for (int i=a;i<n;i++)
- #define per(i,a,n) for (int i=n-1;i>=a;i--)
- #define pb push_back
- #define mp make_pair
- #define all(x) (x).begin(),(x).end()
- #define fi first
- #define se second
- #define SZ(x) ((int)(x).size())
- typedef vector<int> VI;
- typedef long long ll;
- typedef pair<int,int> PII;
- typedef double db;
- mt19937 mrand(random_device{}());
- const ll mod=998244353;
- int rnd(int x) { return mrand() % x;}
- ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
- ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
- // head
- const int N=2010;
- int n,m,nxt[N][N],alive[N];
- char s[N][N];
- bitset<N> sm[N];
- VI ex[N];
- ll ans=0;
- int main() {
- scanf("%d%d",&n,&m);
- for (int i=0;i<n;i++) scanf("%s",s[i]);
- rep(j,0,m) {
- nxt[n-1][j]=n-1;
- per(i,0,n-1) if (s[i][j]==s[i+1][j]) nxt[i][j]=nxt[i+1][j]; else nxt[i][j]=i;
- }
- rep(i,0,n) rep(k,0,m) sm[i][k]=s[i][k]!=s[i][k-1];
- rep(i,0,n) {
- rep(j,i,n) ex[j].clear();
- rep(j,0,m) ex[nxt[i][j]].pb(j);
- rep(j,0,m) alive[j]=1;
- rep(j,i,n) {
- if (j!=i) {
- bitset<N> bs=sm[i]|sm[j];
- int c=alive[0],d=0;
- for (int k=1;k<m;k++) {
- if (bs[k]) c=0;
- if (alive[k]) d+=c,c+=1;
- }
- ans+=d;
- }
- for (auto x:ex[j]) alive[x]=0;
- }
- }
- printf("%lld\n",ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment