回文な問題リストに！！！

問題概要

$M$ × $N$ のグリッドが与えられ、各セルには 0 か 1 の値が書かれている。

今、縦方向と横方向に切れ目を入れて、4 つの長方形に分けて、それぞれの長方形を 180 度回転させる操作を行う。

このときに、各行各列の 1 の個数がすべて変化しないようにしたい。そのような切れ目の入れ方が何通りあるか答えよ。

制約

$2 \le M, N \le 10^{5}$

考えたこと

条件は以下のように言い換えられる

各行ごとに「1 の個数」をカウントしておいたとき、行方向に切れ目を入れたのち、切れ目の前後の「1 の個数」の分布は回文になっている
同じことが列についても言える

ここで、行と列は全く独立に考えられることに注意する。あとは、行と列それぞれについて

どこで切れ目を入れると、前後それぞれが回文になるか

を全探索すればよい。回文判定は Manacher のアルゴリズムを用いれば良い。

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


template<class T> struct ManacherV {
    vector<T> S;
    vector<int> len;

    // construct
    ManacherV(const vector<T> &iS) { init(iS); }
    void init(const vector<T> &iS) {
        S.clear();
        for (int i = 0; i < (int)iS.size(); ++i) {
            S.push_back(iS[i]);
            if (i + 1 < (int)iS.size()) S.push_back(1<<29);
        }
        construct();
    }
    void construct() {
        int N = (int)S.size();
        len.resize(N);
        int i = 0, j = 0;
        while (i < N) {
            while (i-j >= 0 && i+j < N && S[i-j] == S[i+j]) ++j;
            len[i] = j;
            int k = 1;
            while (i-k >= 0 && i+k < N && k+len[i-k] < j) len[i+k] = len[i-k], ++k;
            i += k, j -= k;
        }
    }

    // radius, center is i
    inline int get_odd(int i) { return (len[i*2] + 1) / 2; }

    // radius, center is between i-1 and i
    inline int get_even(int i) { return len[i*2-1] / 2; }

    // judge if [left, right) is palindrome
    inline bool ispalin(int left, int right) {
        int mid = (left + right) / 2;
        if ((right - left) & 1) return ( get_odd(mid) == (right - left + 1)/2);
        else return (get_even(mid) == (right - left)/2);
    }       
};


int M, N;
vector<int> yoko, tate;
int main() {
    cin >> M >> N;
    yoko.assign(M, 0); tate.assign(N, 0);
    for (int i = 0; i < M; ++i) {
        string str; cin >> str;
        for (int j = 0; j < N; ++j) {
            if (str[j] == '1') yoko[i]++, tate[j]++;
        }
    }

    ManacherV<int> m1(yoko), m2(tate);
    long long res1 = 0, res2 = 0;
    for (int i = 1; i < M; ++i) {
        if (m1.ispalin(0, i) && m1.ispalin(i, M)) ++res1;
    }
    for (int i = 1; i < N; ++i) {
        if (m2.ispalin(0, i) && m2.ispalin(i, N)) ++res2;
    }
    cout << res1 * res2 << endl;
}