Submission #2303616

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int solve(vector<vint>bm){
    if(bm.size()==0||bm[0].size()==0)return 1;

    int h=bm.size();
    int w=bm[0].size();

    UnionFindTree uf(h+w);
    rep(i,h)rep(j,w)if(bm[i][j])uf.unite(i,h+j);

    int cnt=h+w;
    rep(i,h+w)if(uf.find(i)==i)cnt--;
    int ret=1;
    rep(i,cnt)ret=ret*2%mod;
    return ret;
}

signed main(){
    int H,W;
    cin>>H>>W;
    vector<string>fld(H);
    rep(i,H)cin>>fld[i];
    int ans=1;
    if(H&1){
        bool flag=false;
        rep(j,W)if(fld[H/2][j]!=fld[H/2][W-1-j])flag=true;
        if(flag)ans=ans*2;
        fld.erase(fld.begin()+H/2);
        H--;
    }

    if(W&1){
        bool flag=false;
        rep(i,H)if(fld[i][W/2]!=fld[H-1-i][W/2])flag=true;
        if(flag)ans=ans*2;
        rep(i,H)fld[i]=fld[i].substr(0,W/2)+fld[i].substr(W/2+1,W/2);
        W--;
    }

    vector<vint>bm(H/2,vint(W/2));
    rep(i,H/2)rep(j,W/2){
        int cnt[26]={};
        cnt[fld[i][j]-'a']++;
        cnt[fld[i][W-1-j]-'a']++;
        cnt[fld[H-1-i][W-1-j]-'a']++;
        cnt[fld[H-1-i][j]-'a']++;
        int w=24;
        rep(k,26){
            for(int l=1;l<=cnt[k];l++)w/=l;
        }
        if(w==24){
            ans=ans*12%mod;
            bm[i][j]=1;
        }
        else{
            ans=ans*w%mod;
        }
    }

    ans=ans*solve(bm)%mod;
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result