Submission #2138151

---

Source Code Expand

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

const int N = 250;
const int mod = 1e9 + 7;

int n, m;
char a[N][N];
int res = 1;
int par[N];

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) { par[anc(p)] = anc(q); }

bool is_palind(string &s) {
    for (int i = 0; i < s.size() / 2; ++i) {
        if (s[i] != s[s.size() - 1 - i]) return false;
    }
    return true;
}

void cut_row() {
    string s = "";
    int mid = n / 2;
    for (int i = 0; i < m; ++i) {
        s += a[mid][i];
    }
    if (!is_palind(s)) {
        res *= 2;
    }
    --n;
    for (int i = mid; i < n; ++i) {
        for (int j = 0; j < m; ++j) a[i][j] = a[i + 1][j];
    }
}

void cut_col() {
    string s = "";
    int mid = m / 2;
    for (int i = 0; i < n; ++i) {
        s += a[i][mid];
    }
    if (!is_palind(s)) {
        res *= 2;
    }
    --m;
    for (int i = mid; i < m; ++i) {
        for (int j = 0; j < n; ++j) a[j][i] = a[j][i + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    if (n & 1) {
        cut_row();
    }
    if (m & 1) {
        cut_col();
    }

    // solve
	for (int i = 0; i < n / 2 + m / 2; ++i) par[i] = i;

    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < m / 2; ++j) {
            vector<char> cur;
            cur.push_back(a[i][j]);
            cur.push_back(a[n - i - 1][j]);
            cur.push_back(a[i][m - j - 1]);
            cur.push_back(a[n - i - 1][m - j - 1]);

            sort(cur.begin(), cur.end());
            int cnt = 0;
            do {
                ++cnt;
            } while(next_permutation(cur.begin(), cur.end()));

			if (cnt == 24) {
				res = 12LL * res % mod;
				join(i, j + n / 2);
			} else {
				res = 1LL * res * cnt % mod;
			}
        }
    }

	int ncomp = 0;
	for (int i = 0; i < n / 2 + m / 2; ++i) {
		if (i == par[i]) {
			++ncomp;
		}
	}

	for (int i = 0; i < n / 2 + m / 2 - ncomp; ++i) {
		res = 2LL * res % mod;
	}

    cout << res << endl;
}

Submission Info

Judge Result