\(2\) つの配置 \(P,Q\) について，それらが「同じ形」であるとは，「各 \(i=1,2,\dots,N\) について，\(P\) の左から \(i\) 列目のブロックの個数と， \(Q\) の左から \(i\) 列目のブロックの個数が等しい」ことであると定義します．

元の配置を \(P\) ，それを \(1\) 回転させて得られる配置を \(P'\) とします．

\(P\) と \(P'\) が同じ形である場合を考えます．\(P\) の各ブロックが \(P'\) のどのマスに移動するのかをシミュレーションで求めます．ブロックの推移関係はサイクルに分解されます．各サイクルの周期の最小公倍数が答えです．

各サイクルの周期を求めます．これは，サイクルに現れるブロックの色を順番に並べた数列の周期となります．数列の周期を求める方法は Z function, prefix function, rolling hash を用いる方法などがあり，サイクルの長さを \(L\) として \(O(L)\) 時間などで動作します．

\(P\) と \(P'\) が同じ形でない場合， \(P'\) を \(1\) 回転させて得られる配置を \(P''\) とすると， \(P\) と \(P''\) は同じ形なので， \(P\) と \(P''\) についての各サイクルの周期の最小公倍数の \(2\) 倍が答えです．

計算量は全体で \(O\left(N+\displaystyle\sum_{i=1}^N M_i\right)\) となります．

実装例

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;

map<long long, int> prime_factor(long long n) {
    map<long long, int> ret;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                ++cnt;
                n /= i;
            }
            ret[i] = cnt;
        }
    }
    if (n != 1) ret[n] = 1;
    return ret;
}

using mint = atcoder::modint998244353;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int N;
    cin >> N;
    vector<int> col;
    vector<vector<int>> blocks(N);  // 各ブロックの通し番号
    vector<int> cnt(N + 1);
    for (int i = 0; i < N; ++i) {
        int M;
        cin >> M;
        blocks[i].resize(M);
        for (int j = 0; j < M; ++j) {
            int c;
            cin >> c;
            col.push_back(c);
            blocks[i][j] = cnt[i] + j;
        }
        cnt[i + 1] = cnt[i] + M;
    }

    auto rotate = [&](const auto& blocks) {
        vector<vector<int>> nblocks(N);
        for (int i = N - 1; i >= 0; --i) {
            for (int j = 0; j < (int)blocks[i].size(); ++j) {
                nblocks[j].push_back(blocks[i][j]);
            }
        }
        return nblocks;
    };

    auto nblocks = rotate(blocks);

    // 1回回転させたものが同じ形でないなら，もう1回回転させる
    bool twice = false;
    for (int i = 0; i < N; ++i) {
        if (blocks[i].size() != nblocks[i].size()) {
            nblocks = rotate(nblocks);
            twice = true;
            break;
        }
    }

    // 各ブロックがどこに移動するか求める
    vector<int> nxt(cnt[N]);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < (int)blocks[i].size(); ++j) {
            nxt[nblocks[i][j]] = cnt[i] + j;
        }
    }

    vector<bool> used(cnt[N]);
    map<int, int> exp;  // 答えを素因数分解した形で持つ
    for (int i = 0; i < cnt[N]; ++i) {
        if (used[i]) continue;

        // サイクルを求める
        int j = i;
        vector<int> cycle;
        while (!used[j]) {
            used[j] = true;
            cycle.push_back(col[j]);
            j = nxt[j];
        }

        // サイクルの周期を求める
        auto z = atcoder::z_algorithm(cycle);
        int period = cycle.size();
        for (int j = 1; j < (int)cycle.size(); ++j) {
            if (cycle.size() % j == 0 && j + z[j] == (int)cycle.size()) {
                period = j;
                break;
            }
        }

        // 答えとの最小公倍数を取る
        for (auto [p, e] : prime_factor(period)) {
            exp[p] = max(exp[p], e);
        }
    }

    mint ans = twice ? 2 : 1;
    for (auto [p, e] : exp) {
        ans *= mint(p).pow(e);
    }
    cout << ans.val() << endl;
}