Codeforces 1815E - Bosco and Particle

首先，对于每个 \(s_i\)，我们只用保留其最小周期，证明显然。

同时以多个光电门为研究对象显然状态数过多，不方便统计。考虑一下连接不同光电门的纽带是什么：显然是相邻光电门之间的空隙。对于每个光电门 \(i\)，如果我们只保留 \(i\) 作为唯一的光电门，那么显然有 \(0\to 1\) 和 \(1\to 2\) 两个间隙，我们通过模拟求出在只保留这一个光电门的前提下 \(0\to 1\) 和 \(1\to 2\) 的次数 \(a_i,b_i\)，那么我们惊奇地发现，在整个过程中，\(i-1\to i\) 的次数和 \(i\to i+1\) 的次数之比就是 \(a_i:b_i\)。

我们假设 \(i\to i+1\) 的经过次数为 \(f_i\)，那么形式化地说，就是 \(\forall i\in[1,n],\exists k_i,s.t.f_{i-1}=a_ik_i,f_{i}=b_ik_i\)，直接暴力对于每个质数求出这个质数在 \(f_0\) 中出现次数的最小值，然后乘起来就得到最小周期中的 \(f_0\) 了。这样就能求出完整的 \(f\) 数组，答案即为 \(2\sum f_i\)。

const int MAXN=2e6;
const int MOD=998244353;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int n,a[MAXN+5],b[MAXN+5],kmp[MAXN+5];char buf[MAXN+5];
int pr[MAXN+5],prcnt,vis[MAXN+5],mnp[MAXN+5];
void sieve(int n){
	for(int i=2;i<=n;i++){
		if(!vis[i])pr[++prcnt]=i,mnp[i]=i;
		for(int j=1;j<=prcnt&&pr[j]*i<=n;j++){
			vis[pr[j]*i]=1;mnp[i*pr[j]]=pr[j];
			if(i%pr[j]==0)break;
		}
	}
}
vector<pii>vec[MAXN+5];
int prd=1;
int main(){
	scanf("%d",&n);sieve(MAXN);
	for(int i=1;i<=n;i++){
		scanf("%s",buf+1);int len=strlen(buf+1);
		for(int j=1;j<=len;j++)kmp[j]=0;
		for(int j=2,k=0;j<=len;j++){
			while(k&&buf[j]!=buf[k+1])k=kmp[k];
			if(buf[j]==buf[k+1])++k;kmp[j]=k;
		}
		int nl=((len%(len-kmp[len])==0)?(len-kmp[len]):len),cur=0,dir=1,pt=1;
		do{
			if((cur==0&&dir==-1)||(cur==2&&dir==1))dir=-dir;
			if(dir==1)((!cur)?a[i]:b[i])++;
			cur+=dir;
			if(cur==1){
				if(buf[pt]=='1')dir=-dir;
				pt=pt%nl+1;
			}
		}while(cur!=0||pt!=1);
//		printf("! %d %d\n",a[i],b[i]);
	}
	int lim=n;
	for(int i=1;i<=n;i++)if(!b[i]){lim=i-1;break;}
	for(int i=1;i<=lim;i++){
		int tmp=b[i];
		while(tmp!=1){
			int p=mnp[tmp],cnt=0;
			while(tmp%p==0)tmp/=p,cnt++;
			vec[p].pb(mp(cnt,1));
		}
		tmp=a[i];
		while(tmp!=1){
			int p=mnp[tmp],cnt=0;
			while(tmp%p==0)tmp/=p,cnt++;
			vec[p].pb(mp(-cnt,1));
		}
		tmp=b[i];
		while(tmp!=1){
			int p=mnp[tmp],cnt=0;
			while(tmp%p==0)tmp/=p,cnt++;
			vec[p].pb(mp(cnt,2));
		}
	}
	for(int i=1;i<=prcnt;i++){
		int mx=0,cur=0;
		for(pii p:vec[pr[i]]){
			if(p.se==1)cur+=p.fi,chkmax(mx,-cur);
			else chkmax(mx,p.fi-cur);
		}
		prd=1ll*prd*qpow(pr[i],mx)%MOD;
	}
	int sum=prd;
	for(int i=1;i<=lim;i++){
		prd=1ll*prd*qpow(a[i],MOD-2)%MOD*b[i]%MOD;
		sum=(sum+prd)%MOD;
	}printf("%d\n",2*sum%MOD);
	return 0;
}