Submission #994519

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const int mod = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= mod)
    x -= mod;
  return x;
}

int udd(int &x, int y) {
  return x = add(x, y);
}

int sub(int x, int y) {
  return add(x, mod - y);
}

int mul(ll x, ll y) {
  return x * y % mod;
}

int uul(int &x, int y) {
  return x = mul(x, y);
}

const int M = 239;
const int N = 103 * 103;

bitset<N> b[M];
int low[M];
int m = 0;

void add(bitset<N> x) {
  for (int i = 0; i < m; ++i)
    if (x[low[i]]) {
      x ^= b[i];
    }
  
  if (x.count()) {
    b[m] = x;
    for (int i = 0; i < N; ++i)
      if (x[i]) {
        low[m] = i;
        break;
      }
    ++m;
  }
}

int h, w;
string s[M];
int ans = 1;
bool u[M][M];


bool isPal(string s) {
  int n = s.length();
  for (int i = 0; i < n; ++i)
    if (s[i] != s[n - 1 - i])
      return false;
  return true;
}

int perm(string s) {
  set<string> ans;
  for (int i = 0; i < 24; ++i) {
    ans.insert(s);
    next_permutation(s.begin(), s.end());
  }
  //cout << "s = " << s << endl;
  //cout << "sz = " << ans.size() << endl;
  return ans.size();
}

void read() {
  cin >> h >> w;
  for (int i = 0; i < h; ++i)
    cin >> s[i];

  if (h % 2 == 1) {
    if (!isPal(s[h / 2]))
      uul(ans, 2);
  }

  if (w % 2 == 1) {
    string cur = "";
    for (int i = 0; i < h; ++i)
      cur.push_back(s[i][w / 2]);
    if (!isPal(cur))
      uul(ans, 2);
  }
}

void kill() {
  for (int i = 0; i < h - 1 - i; ++i)
    for (int j = 0; j < w - 1 - j; ++j) {
      string cur = "";
      for (int a : {i, h - i - 1})
        for (int b : {j, w - j - 1})
            cur.push_back(s[a][b]);

      int sz = perm(cur);
      if (sz == 24) {
        u[i][j] = true;
        uul(ans, 12);
      } else {
        uul(ans, sz);
      }
    }

  for (int i = 0; i < h - i - 1; ++i) {
    bitset<N> x;
    for (int j = 0; j < w - 1 - j; ++j)
      if (u[i][j]) {
        x[i * 102 + j] = 1;
      }
    add(x);
  }

  for (int j = 0; j < w - 1 - j; ++j) {
    bitset<N> x;
    for (int i = 0; i < h - 1 - i; ++i)
      if (u[i][j])
        x[i * 102 + j] = 1; 
    add(x);
  }

  for (int i = 0; i < m; ++i)
    uul(ans, 2);

  cout << ans << endl;
}

int main() {
#ifdef LOCAL
  assert(freopen("i.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  read();
  kill();
}

Submission Info

Judge Result