题解：P7114 [NOIP2020] 字符串匹配

· · 题解

简单数数题，不需要用到 KMP。

考虑 S=(AB)^tC，C 是 S 的后缀，(AB)^t 是 S 的前缀。所以可以枚举作为 C 的后缀 [i,n]，考虑 [1,i) 划分成 (AB)^t 的方案数，全部加起来即答案。

为了应对 F(A)\le F(C) 的限制，可以扫两遍求出前缀和后缀的 F，分别记作 p(i),q(i)。

显然一段前缀 S[1,i]=(AB)^t 由一段更小的前缀 S[1,j]=AB 多次拼接构成。所以可以先求出将每个前缀拆成 AB 的方案数，再枚举每个前缀长度的倍数，把方案数贡献上去。具体地，设 f(i,j) 表示前缀 [1,i) 拆出来的 F(A)\le j 的方案数，有

f(i,j)=\sum_{k=1}^{i-1} [p(k)\le j]

容易前缀和递推求出。再记 g(i,j) 表示把 [1,i) 拆成 (AB)^t 的方案数，对它产生贡献的只有可能是 k|i 的 f(k,j)。对每个 i 枚举 k 是 O(n\sqrt n) 的，考虑对一个 k 枚举所有倍数 i，是 O(n\ln n) 的。那么 k 对 i 有贡献当且仅当 k 对 i-k 有贡献且 S[1,k]=S[i-k+1,i]，哈希判断即可。

这样求出所有 g(i,j)，答案就是

\sum_{i=3}^ng(i-1,q(i))

时间复杂度 O(|\Sigma|n\ln n)，不够优秀。考虑枚举倍数 i 计算 g 的时候直接把贡献加入答案，即直接把 f(k,q(i+1)) 加到答案上，时间复杂度 O(n(|\Sigma|+\ln n))。

// Problem: P7114 [NOIP2020] 字符串匹配
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7114
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<20)+5;
const int mod=1e9+123;

int n,base,pw[N],h[N];
ll as;
string s;

int hs(int l,int r){return (h[r]-1ll*h[l-1]*pw[r-l+1]%mod+mod)%mod;}

int p[N],q[N],cnt[26],f[27][N];

void init(){
    mt19937 rnd(time(0));
    base=rnd()%mod,pw[0]=1;
    for(int i=1;i<=N-5;++i) pw[i]=1ll*pw[i-1]*base%mod;
}

void solve(){
    cin>>s,n=s.size(),s=" "+s,as=0;
    for(int i=1;i<=n;++i) h[i]=(1ll*h[i-1]*base%mod+(int)s[i])%mod;
    memset(cnt,0,sizeof cnt);
    for(int i=1;i<=n;++i){
        if(cnt[s[i]-'a']) p[i]=p[i-1]-1;
        else p[i]=p[i-1]+1;
        cnt[s[i]-'a']^=1;
    }
    memset(cnt,0,sizeof cnt);
    for(int i=n;i;--i){
        if(cnt[s[i]-'a']) q[i]=q[i+1]-1;
        else q[i]=q[i+1]+1;
        cnt[s[i]-'a']^=1;
    }
    for(int j=0;j<=26;++j) for(int i=2;i<=n;++i) f[j][i]=f[j][i-1]+(p[i-1]<=j); 

    for(int i=2;i<=n;++i){
        int val=hs(1,i);
        for(int j=i;j<n;j+=i){
            if(hs(j-i+1,j)==val) as+=f[q[j+1]][i];
            else break;
        }
    }
    cout<<as<<"\n";
    for(int i=1;i<=n;++i) q[i]=0;
}

signed main(){
    // freopen("string.in","r",stdin);
    // freopen("string.out","w",stdout);
    init();
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}