Submission #1005635

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

const int MOD = 1000000007;

int root[1000];
int getRoot(int v){ return root[v] == -1 ? v : root[v] = getRoot(root[v]); }

int main(){
	int H, W;
	while(cin >> H >> W){
		vector<string> vs(H);
		for(int i=0;i<H;i++) cin >> vs[i];
		long long res = 1;
		if(H%2 == 1){
			bool ok = false;
			for(int i=0;i<W/2;i++){
				if(vs[H/2][i] != vs[H/2][W-1-i]) ok = true;
			}
			if(ok) res *= 2;
		}
		if(W%2 == 1){
			bool ok = false;
			for(int i=0;i<H/2;i++){
				if(vs[i][W/2] != vs[H-1-i][W/2]) ok = true;
			}
			if(ok) res *= 2;
		}
		if(H == 1 || W == 1){
			cout << res << endl;
			continue;
		}
		memset(root, -1, sizeof(root));
		int comp = H/2 + W/2;
		for(int i=0;i<H/2;i++){
			for(int j=0;j<W/2;j++){
				vector<int> cnt(26, 0);
				const int ri = H-1-i;
				const int rj = W-1-j;
				cnt[vs[i][j]-'a']++;
				cnt[vs[i][rj]-'a']++;
				cnt[vs[ri][j]-'a']++;
				cnt[vs[ri][rj]-'a']++;
				int p = 24;
				for(int k=0;k<26;k++){
					if(cnt[k] == 2) p /= 2;
					if(cnt[k] == 3) p /= 6;
					if(cnt[k] == 4) p /= 24;
				}
				if(p == 24){
					p /= 2;
					int a = getRoot(i);
					int b = getRoot(j+500);
					if(a != b){
						--comp;
						root[b] = a;
					}
				}
				res *= p;
				res %= MOD;
			}
		}
		comp = (H/2+W/2)-comp;
		for(int i=0;i<comp;i++) res = (2*res)%MOD;
		cout << res << endl;
	}
}

Submission Info

Judge Result