好像不难。但是没想到。
首先这玩意看起来就得拆开，要不然完全做不了。
假如我们只考虑某一个点 \(i\)，考虑 \(i - 1 \to i, i \to i + 1\) 这两条边的经过次数，不难发现其它的点是不会影响这两条边的。那么我们可以直接依据题意模拟，只考虑这一个点的周期是多长，然后所有的周期 \(\mathrm{lcm}\) 起来就完了...吗？
虽然经过次数互不影响，但是它们经过还是有顺序的，而不是同步的，所以直接对周期求 \(\mathrm{lcm}\) 是错的。我们考虑如何将这些周期联系起来，发现每相邻两个点共用一条边，那么我们考虑每条边经过了多少次而不是每个点经过了多少次。这样，依照题意模拟后，我们可以得到经过 \(a_i\) 次 \(i - 1 \to i\)，\(b_i\) 次 \(i \to i + 1\)。那么我们设 \(f_i\) 表示 \(i \to i + 1\) 经过了多少次，那么可以得到 \(f_{i - 1} = a_i k_i, f_i = b_i k_i\)。我们需要找出最小的 \(f_i\)。考虑固定住 \(f_0\)，那么其它的 \(f_i, k_i\) 都可以得到，我们只需要保证这些都是正整数即可。我们分每一个质因子去考虑，跑一遍贪心就能得到每个质因子至少是多少了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005, P = 998244353;
int n;
char s[MAXN];
int nxt[MAXN];
int a[MAXN], b[MAXN];
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
int pri[MAXN], pcnt;
int mnp[MAXN];
void sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!mnp[i]) mnp[i] = i, pri[++pcnt] = i;
for (int j = 1; j <= pcnt && i * pri[j] <= n; j++) {
mnp[i * pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
}
int cc[MAXN];
int main() {
sieve(1000000);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
int m = strlen(s + 1);
for (int i = 2, j = 0; i <= m; i++) {
while (j && s[i] != s[j + 1]) j = nxt[j];
if (s[i] == s[j + 1]) j++;
nxt[i] = j;
}
m = (m % (m - nxt[m]) == 0 ? (m - nxt[m]) : m);
int cur = 0, dir = 0, ptr = 1;
do {
if (cur == 0) cur = 1, dir = 1, a[i]++;
else if (cur == 2) cur = 1, dir = -1;
else {
if (s[ptr] == '1') dir *= -1;
if (dir == 1) b[i]++;
cur += dir;
if (ptr == m) ptr = 1;
else ptr++;
}
} while (!(cur == 0 && ptr == 1));
// printf("%d %d\n", a[i], b[i]);
}
int f = 1;
for (int i = 1; i <= n; i++) {
if (!b[i]) break;
int tmp = a[i];
while (tmp != 1) {
int p = mnp[tmp];
tmp /= p;
cc[p]--;
if (cc[p] < 0) f = 1ll * f * p % P, cc[p] = 0;
}
tmp = b[i];
while (tmp != 1) {
int p = mnp[tmp];
tmp /= p;
cc[p]++;
}
}
int ans = f;
for (int i = 1; i <= n; i++) {
f = 1ll * f * qpow(a[i], P - 2) % P * b[i] % P;
ans = (ans + f) % P;
}
ans = 2ll * ans % P;
printf("%d\n", ans);
return 0;
}