Submission #995271

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

template<class T>
T pow(T x, ll n, T r = 1) {
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
struct ModInt {
    uint v;
    ModInt() : v{0} {}
    ModInt(ll v) : v{normS(v%MD+MD)} {}
    static uint normS(const uint &x) {return (x<MD)?x:x-MD;};
    static ModInt make(const uint &x) {ModInt m; m.v = x; return m;}
    ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));}
    ModInt operator-(const ModInt &r) const {return make(normS(v+MD-r.v));}
    ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);}
    ModInt& operator+=(const ModInt &r) {return *this=*this+r;}
    ModInt& operator-=(const ModInt &r) {return *this=*this-r;}
    ModInt& operator*=(const ModInt &r) {return *this=*this*r;}
    static ModInt inv(const ModInt &x) {
        return pow(ModInt(x), MD-2);
    }
};
using Mint = ModInt<TEN(9)+7>;

// using B = vector<string>;
// set<B> s;
// void dfs(B b) {
//     if (s.count(b)) return;
//     s.insert(b);
//     cout << b[0] << endl << b[1] << endl;
//     swap(b[0][0], b[0][1]);
//     dfs(b);
//     swap(b[0][0], b[0][1]);
//     swap(b[0][0], b[1][0]);
//     dfs(b);
//     swap(b[0][0], b[1][0]);
//     swap(b[1][0], b[1][1]);
//     dfs(b);
//     swap(b[1][0], b[1][1]);
//     swap(b[0][1], b[1][1]);
//     dfs(b);
//     swap(b[0][1], b[1][1]);
// }

const int MN = 220;
using P = pair<int, int>;

Mint off = 1;

int co(vector<char> v) {
    sort(v.begin(), v.end());
/*    for (char c: v) {
        cout << c;
    } cout << endl;*/
    set<vector<char>> s;
    do {
        s.insert(v);
    } while (next_permutation(v.begin(), v.end()));
    return int(s.size());
}

bool coun(vector<char> v) {
    int u = co(v);
    if (u != 24) {
        off *= u;
        return false;
    }
    return true;
}

char g[MN][MN];
Mint d[MN][MN];

int main() {
    cout << setprecision(20);
    int h, w;
    cin >> h >> w;

    for (int y = 0; y < h; y++) {
        string s;
        cin >> s;
        for (int x = 0; x < w; x++) {
            g[y][x] = s[x];
        }
    }

    if (h % 2) {
        string s1, s2;
        for (int x = 0; x < w; x++) {
            s1 += g[h/2][x];
            s2 += g[h/2][w-1-x];
        }
        if (s1 != s2) off *= 2;
    }
    if (w % 2) {
        string s1, s2;
        for (int x = 0; x < h; x++) {
            s1 += g[x][w/2];
            s2 += g[h-1-x][w/2];
        }
        if (s1 != s2) off *= 2;
    }

    if (min(h, w) == 1) {
        cout << off.v << endl;
        return 0;
    }

    int buf = 0;
    vector<int> yv, xv;
    for (int a = 0; a < h; a++) {
        int b = h-1-a;
        if (a >= b) continue;
        for (int c = 0; c < w; c++) {
            int d = w-1-c;
            if (c >= d) continue;
            vector<char> v;
            v.push_back(g[a][c]);
            v.push_back(g[a][d]);
            v.push_back(g[b][c]);
            v.push_back(g[b][d]);
            bool u = coun(v);
            if (u) {
                yv.push_back(a);
                xv.push_back(c);
                off *= 12;
            }
        }
    }
    sort(yv.begin(), yv.end());
    yv.erase(unique(begin(yv), end(yv)), end(yv));
    sort(xv.begin(), xv.end());
    xv.erase(unique(begin(xv), end(xv)), end(xv));

    int co = yv.size()+xv.size();
    co--;
    if (co >= 0) {
        off *= pow(Mint(2), co);
    }
    cout << off.v << endl;
    return 0;
}

Submission Info

Judge Result