Submission #4140302

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

char c[209][209]; long long H, W, mod = 1000000007;
bool usedx[209], usedy[209];

bool isdifferent(string V) {
	for (int i = 0; i < V.size(); i++) {
		for (int j = i + 1; j < V.size(); j++) { if (V[i] == V[j]) return false; }
	}
	return true;
}

int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) cin >> c[i][j];
	}
	if (H == 1) {
		string s1 = ""; for (int i = 0; i < W; i++) s1 += c[0][i];
		string s2 = ""; for (int i = W - 1; i >= 0; i--) s2 += c[0][i];
		if (s1 == s2) cout << "1" << endl;
		else cout << "2" << endl;
		return 0;
	}
	else if (W == 1) {
		string s1 = ""; for (int i = 0; i < H; i++) s1 += c[i][0];
		string s2 = ""; for (int i = H - 1; i >= 0; i--) s2 += c[i][0];
		if (s1 == s2) cout << "1" << endl;
		else cout << "2" << endl;
		return 0;
	}

	string b1 = ""; if (H % 2 == 1) { for (int i = 0; i < W; i++) b1 += c[H / 2][i]; }
	string b2 = ""; if (W % 2 == 1) { for (int i = 0; i < H; i++) b2 += c[i][W / 2]; }

	long long sum = 1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (!(i <= (H - 1 - i) && j <= (W - 1 - j))) continue;

			vector<tuple<int, int, int>>vec;
			vec.push_back(make_tuple(1, i, j));
			if (j != (W - 1 - j)) vec.push_back(make_tuple(2, i, W - 1 - j));
			if (i != (H - 1 - i)) vec.push_back(make_tuple(3, H - 1 - i, W - 1 - j));
			if (i != (H - 1 - i) && j != (W - 1 - j)) vec.push_back(make_tuple(4, H - 1 - i, j));
			sort(vec.begin(), vec.end());

			vector<string>ans, ans2; bool flag = false;
			do {
				vector<int>E; for (int k = 0; k < vec.size(); k++) E.push_back(get<0>(vec[k]));

				int ret = 0;
				for (int k = 0; k < E.size(); k++) { for (int l = k + 1; l < E.size(); l++) { if (E[k] > E[l]) ret++; } }
				if (ret % 2 == 0) {
					string rem = "";
					for (int k = 0; k < E.size(); k++) rem += c[get<1>(vec[k])][get<2>(vec[k])];
					ans.push_back(rem);

					if (rem.size() == 4 && isdifferent(rem) == true) flag = true;
				}
			} while (next_permutation(vec.begin(), vec.end()));

			sort(ans.begin(), ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end());
			sum *= (long long)(ans.size()); sum %= mod;

			if (flag == true) {
				usedx[i] = true;
				usedy[j] = true;
			}
		}
	}
	bool flag = false;
	for (int i = 0; i < H / 2; i++) { if (usedx[i] == true) { sum *= 2; sum %= mod; flag = true; } }
	for (int i = 0; i < W / 2; i++) { if (usedy[i] == true) { sum *= 2; sum %= mod; flag = true; } }
	if (flag == true) {
		if (sum % 2 == 1)sum += mod;
		sum /= 2;
	}
	string c1 = b1; reverse(c1.begin(), c1.end()); if (b1 != c1) { sum *= 2; sum %= mod; }
	string c2 = b2; reverse(c2.begin(), c2.end()); if (b2 != c2) { sum *= 2; sum %= mod; }
	cout << sum << endl;
	return 0;
}

Submission Info

Judge Result