Solution P7546
henryhu2006
·
·
题解
题意概括
定义字符串一个位置的魔力值等于下标的约数个数，字符串的一个连续子串的魔力值为各个位置的魔力值之和。
定义字符串的一个连续子串是纯净的，当且仅当可以将这个子串分为等长的 x 段，每段长度为 len，任意两段的相同位置的字符不同，且要求 x\ge S, len\in [l,r]。
求纯净的连续子串中最大魔力值。
数据范围：n\le 5\times 10^5，r-l\le10，字符集大小为 52。
题解
发现 r-l\le10，因此可以枚举段的长度。
考虑以 l 为左端点的连续子串，对于任意 r_1,r_2，l\le r_1<r_2，当 [l,r_1] 和 [l,r_2] 均纯净时，[l,r_1] 的代价必然小于 [l,r_2]，因为约数个数不可能是非正的。
对于每个位置，无论它处于哪个子串，导致不纯净的一定是在模 len 意义下和它同模的坐标。
定义 suf_i=\min \{j|j>i,j \equiv i\ (\text{mod} \ len) ,s_j=s_i\}。
接着枚举 $l$，则最大段数为 $x=\lfloor \frac{\min_{i=l}^{n}suf_i}{len} \rfloor$，如果 $x\ge S$，那么以 $[l,l+x\times len-1]$ 更新答案。
一开始预处理一下约数个数的前缀和，总时间复杂度 $\Theta((r-l)\times 52n)$，精细实现可以做到 $\Theta((r-l)\times n)$。
## 代码
细节：不能将 $len$ 和 $S$ 无脑相乘，会爆 `int`。
```cpp
#include<bits/stdc++.h>
#define rint register int
using namespace std;
const int N=5e5+5;
int n,l,r,S,ans;
int num[N],vis[N],sum[N];
int now[N][52],suf[N];
char s[N];
int main(){
cin>>n>>l>>r>>S;
scanf("%s",s+1),num[1]=1;
for(rint i=1;i<=n;++i)
if(s[i]>='a') s[i]-='a'-26;
else s[i]-='A'; // 压缩字符集
for(rint i=2;i<=n;++i){
if(!vis[i]) vis[i]=i;
rint cnt=0,j=i;
while(j%vis[i]==0) j/=vis[i],++cnt;
num[i]=num[j]*(cnt+1);
if(num[i]>2) continue;
for(j=i*2;j<=n;j+=i) vis[j]=i; // 处理约数个数
}
for(rint i=1;i<=n;++i)
sum[i]=sum[i-1]+num[i];
for(rint len=l;len<=r;++len){
if(1ll*len*S>n) break;
memset(now,0,208*(len+1)); // memset 乘以 52 也跑得飞快
memset(suf,0,sizeof(suf));
for(rint j=n,mo=n%len,res=n+1;j>=1;--j,--mo){
if(mo<0) mo=len-1;
if(now[mo][s[j]]) suf[j]=now[mo][s[j]];
else suf[j]=n+1;
res=min(res,suf[j]);
int zq=(res-j)/len;
if(zq>=S) ans=max(ans,sum[j+zq*len-1]-sum[j-1]);
now[mo][s[j]]=j;
}
}
cout<<ans;
return 0;
}
```