专栏文章

题解：P5404 [CTS2019] 重复

UUnion_of_Britainschanghang
P5404题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip38mzm
此快照首次捕获于
2025/12/03 05:26
3 个月前
此快照最后确认于
2025/12/03 05:26
3 个月前
查看原文
下文 MSET⁡\operatorname{MSET} 同无标号无根树计数使用的 MSET⁡\operatorname{MSET} 变换。两边取 ln⁡\ln 即可在 O(nlog⁡n)O(n\log n) 内时间计算其逆。
限制只需考虑所需统计字符串 tt 的最小表示法。若希望 tt 本身是其最小表示法，则 tt 是 lyndon 串的若干重复。如果 t=t′kt=t'^{k}，则 t′t' 对答案贡献为 m/km/k。因此下面只考虑 tt 本身是 lyndon 串（记为 t∈Lt\in L）的情况。
如果没有字典序小于 ss 的限制：由于每个字符串有唯一的 lyndon 分解 S=T1:mS=T_{1:m}，满足 Ti≥Ti+1，Tj∈LT_{i}\ge T_{i+1}，T_j\in L，因此设所有字符串的生成函数是 SS，有：
MSET⁡(L)=S\operatorname{MSET}(L)=S
逆变换 MSET 即可求出。
加入限制后，希望保留 MSET⁡\operatorname{MSET} 的统计法。此时，仅保留 ss 分解的第一个 lyndon 串 s1s_1 并重复之使得长度为 mm，记为 s1′s_1'。此时取所有字典序 ≤s1′\le s_1' 的 lyndon 串集合 L′L'，MSET⁡(L)\operatorname{MSET}(L) 即为字典序 <s<s 的字符串集合带上 s1s_1。
原因是考虑两字符串 s,ts,t 的比较。如果 ∣s1∣>∣t1∣|s_1|> |t_1|，由于 t2≤t1t_2\le t_1 和 s1∈Ls_1\in L，若 t1t_1 是 s1s_1 的前缀，t2:mt_{2:m} 必能决定 t<st<s；
否则，∣s1∣≤∣t1∣|s_1|\le |t_1|，这只会在 s1s_1 是 t1t_1 的前缀时产生疑问。但由于 t1≤s1′t_1\le s_1'，则 t1t_1 在 ∣s1∣|s_1| 后的位置仍然 ≤s1\le s_1，而此时 t1t_1 开头就并非最小后缀（不如去掉 s1s_1 后的后缀），这就产生了矛盾。
上面是小于等于。但是由于 lyndon 串不存在小于长度的周期，实际上取等只在 s1s_1。这就说明了正确性。
瓶颈在逆 MSET 变换，时间复杂度 O(mlog⁡m)O(m\log m)。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5,mod=998244353,g=3,ig=(mod+1)/3;
int lim,L,r[maxn];
void predo(int n){
	lim=1,L=0;
	while(lim<=n)lim<<=1,L++;
	for(int i=1;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)<<L-1);
}
#define Poly vector<int> 
int qp(int a,int b){
	if(b==0)return 1;
	int T=qp(a,b>>1);T=T*T%mod;
	if(b&1)return T*a%mod;
	return T;
}
void ntt(Poly &a,int tp){
	for(int i=0;i<lim;i++)if(r[i]>i)swap(a[i],a[r[i]]);
	for(int mid=1;mid<lim;mid<<=1){
		int wn=qp(tp==1?g:ig,(mod-1)/(mid<<1));
		for(int j=0;j<lim;j+=(mid<<1)){
			int W=1;
			for(int k=0;k<mid;k++,W=W*wn%mod){
				int x=a[j+k],y=a[j+k+mid]*W%mod;
				a[j+k]=(x+y)%mod,a[j+k+mid]=(x-y+mod)%mod;
			}
		}
	}
	if(tp==-1){
		int I=qp(lim,mod-2);
		for(int i=0;i<lim;i++)a[i]=a[i]*I%mod;
	}
}
Poly operator +(Poly a,Poly b){
	Poly c(max(a.size(),b.size()));
	for(int i=0;i<c.size();i++){
		c[i]=0;
		if(a.size()>i)c[i]+=a[i];
		if(b.size()>i)c[i]+=b[i];
		c[i]%=mod;
	}
	return c;
}
Poly operator -(Poly a,Poly b){
	Poly c(max(a.size(),b.size()));
	for(int i=0;i<c.size();i++){
		c[i]=0;
		if(a.size()>i)c[i]+=a[i];
		if(b.size()>i)c[i]-=b[i]-mod;
		c[i]%=mod;
	}
	return c;
}
Poly operator *(Poly a,Poly b){
	Poly A=a,B=b,c;
	predo(a.size()+b.size());
	A.resize(lim),B.resize(lim);c.resize(lim);
	ntt(A,1);ntt(B,1);
	for(int i=0;i<lim;i++)c[i]=A[i]*B[i]%mod;
	ntt(c,-1);
	c.resize(a.size()+b.size()-1);
	return c;
}
Poly inv(const Poly &a,int len){
	if(len==1){
		Poly b(1);
		b[0]=qp(a[0],mod-2);
		return b;
	}
	Poly b=inv(a,(len+1)>>1),c(len);
	for(int i=0;i<len;i++)c[i]=a[i];
	predo(len*2-1);
	b.resize(lim),c.resize(lim);
	ntt(c,1);ntt(b,1);
	for(int i=0;i<lim;i++)b[i]=(2-b[i]*c[i]%mod+mod)%mod*b[i]%mod;
	ntt(b,-1);b.resize(len);
	return b;
}
Poly ln(const Poly &a,int len){
	Poly b=inv(a,len),F(len-1);
	for(int i=0;i<len-1;i++)F[i]=(i+1)*a[i+1]%mod;
	b=b*F;b.resize(len);
	for(int i=len-1;i>0;i--)b[i]=b[i-1]*qp(i,mod-2)%mod;
	b[0]=0;
	return b;
}
Poly deriv(Poly a){
	if(a.size()==1)return (Poly){0};
	Poly b;b.resize(a.size()-1);
	for(int i=1;i<a.size();i++)b[i]=i*a[i]%mod;
	return b;
}
Poly integ(Poly a){
	Poly b;b.resize(a.size()+1);
	for(int i=0;i<a.size();i++)b[i+1]=a[i]*qp(i+1,mod-2)%mod;
	return b;
}
Poly exp(const Poly &a,int len){
	if(len==1)return (Poly){1};
	Poly b=exp(a,(len+1)>>1);b.resize(len);Poly lnb=ln(b,len);
	for(int i=0;i<len;i++)lnb[i]=(a[i]-lnb[i]+mod)%mod;
	(lnb[0]+=1)%=mod;
	b=b*lnb;b.resize(len);
	return b;
}
vector<int> fac[maxn];
Poly NMSET(Poly A){
	int n=A.size();
	Poly B=ln(A,n),res(n);
	for(int i=1;i<n;i++){
		res[i]=B[i];
		for(auto j:fac[i])if(j<i)(res[i]+=mod-res[j]*qp(i/j,mod-2)%mod)%=mod;
	}
	return res;
}
string t;char s[maxn],S[maxn];
int n,dL[maxn],dR[maxn],cnt=0,m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	for(int i=1;i<=2000;i++)for(int j=i;j<=2000;j+=i)fac[j].push_back(i);
	cin>>m>>t;n=t.size();
	for(int i=1;i<=n;i++)s[i]=t[i-1];
	for(int i=1;i<=n;){
		int j=i,k=i+1;
		while(k<=n&&s[j]<=s[k]){
			if(s[j]==s[k])++j;
			else j=i;
			++k;
		}
		while(i<=j){
			dL[++cnt]=i,dR[cnt]=i+(k-j)-1;
			i+=k-j;
		}
	}
	for(int l=1,r;l<=m;l=r+1){
		r=l+dR[1]-1;int cr=min(r,m);
		for(int j=l;j<=r;j++)S[j]=s[j-l+1];
	}int ans=0;
	int I=qp(26,mod-2),z=1,cr=0;
	Poly F(m+1);
	for(int i=1;i<=m;i++){
		z=z*I%mod;(cr+=(S[i]-'a')*z)%=mod;
		F[i]=qp(26,i)*cr%mod;
	}
	for(int i=0;i<=m;i++)F[i]++;
	Poly G=NMSET(F);
	if(dR[1]<=m)G[dR[1]]--;
	for(auto x:fac[m])(ans+=G[x]*x)%=mod;
	cout<<ans<<endl;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...