链接：link
希望能苟到这些题发挥用处的时候。
A - 排水系统
topsort。
B - 报数
埃筛。
C - 种花
模拟。
D - 涂色游戏
E - 字符串匹配
我会 hashing！考虑枚举 \(AB\) 和 \(i\)，hash 判断是否相同，于是 \(C\) 是剩下的，可以得到。发现 \(A,C\) 都只会是一段前缀/后缀，于是预处理任意前后缀的 \(F\)，假设 \(AB=s[1\ldots p]\)，相当于统计有多少个 \(t\) 满足 \(t\in[1,p)\) 且 \(F(s[1\ldots t])\le F(C)\)，开个桶即可。复杂度 \(\mathcal{O}(n\ln n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int inf=1e18;
const ull BASE=1145141;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
ull pw[2000005],h[2000005];char s[2000005];
ull calc(int l,int r){
return h[r]-h[l-1]*pw[r-l+1];
}
int sum[55],c[55],pre[2000005],suf[2000005];
void solve(){
scanf("%s",s+1);int n=strlen(s+1),cnt,ans=0;pre[0]=suf[n+1]=0;
for(int i=0;i<=26;i++)sum[i]=0;
for(int i=0;i<26;i++)c[i]=0;
cnt=0;for(int i=1;i<=n;i++)cnt-=c[s[i]-'a'],c[s[i]-'a']^=1,cnt+=c[s[i]-'a'],pre[i]=cnt;
for(int i=0;i<26;i++)c[i]=0;
cnt=0;for(int i=n;i>=1;i--)cnt-=c[s[i]-'a'],c[s[i]-'a']^=1,cnt+=c[s[i]-'a'],suf[i]=cnt;
for(int i=1;i<=n;i++)h[i]=h[i-1]*BASE+s[i];
for(int i=1;i<n;i++){
ull val=calc(1,i);
for(int j=1;j*i<n;j++){
if(calc((j-1)*i+1,j*i)!=val)break;
ans+=sum[suf[j*i+1]];
}
for(int j=pre[i];j<=26;j++)sum[j]++;
}
printf("%lld\n",ans);
}
signed main(){
pw[0]=1;
for(int i=1;i<=(1ll<<20);i++)pw[i]=pw[i-1]*BASE;
int T=read();
while(T--)solve();
return 0;
}