首先考虑O(n^3)的暴力怎么写。

显然，可以枚举字符串\(A\)+\(B\)的右端点，左端点显然是1，暴力判断是否能与后面的字符构成循环节，对于满足

\(k*(A+B)+C=\) 整个字符串\((k \in Z)\)

的情况暴力枚举\(A\),\(B\)分界点，对于\(L(x)\le R(x)\)的情况统计答案即可，\(L(x)\)为\(1\)到\(n\)出现奇数次的字符数量，\(R(x)\)为\(x\)到\(n\)出现奇数次的字符数量。

其实这样由于\(A+B\)很难找到循环节，均摊下来时间复杂度在随机数据下远小于\(O(n^{3})\),可以拿到\(48pts\)了，美滋滋。

把暴力贴上来吧：

#include<bits/stdc++.h>
#define LL long long
#define N (1<<20)+50
using namespace std;

LL ans;
int t,len;
char a[N];
int toa[30],toc[30],jia[N],jic[N];

inline int qr()
{
    char a=0;int x=0,w=1;
    while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
    while(a<='9'&&a>='0'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
    return x*w;
}

int main()
{
    t=qr();
    while(t--)
    {
        scanf("%s",(a+1));
        len=strlen(a+1);
        memset(toa,0,sizeof(toa));
        memset(toc,0,sizeof(toc));
        memset(jic,0,sizeof(jic));
        memset(jia,0,sizeof(jia));
        ans=0;
        for(register int i=1;i<=len;i++)//计算L(i)
        {
            toa[a[i]-'a']++;
            toa[a[i]-'a']&1 ? jia[i]=jia[i-1]+1 :jia[i]=jia[i-1]-1;
        }
        for(register int i=len;i>=1;i--)//计算R(i)
        {
            toc[a[i]-'a']++;
            toc[a[i]-'a']&1 ? jic[i]=jic[i+1]+1 :jic[i]=jic[i+1]-1;
        }
        for(register int i=2;i<len;i++)
        {
            int flag=1;
            for(register int k=1;k<i;k++)//特判k=1的情况
                if(jia[k]<=jic[i+1])
                    ans++;
            for(register int j=2;j*i<len;j++)//枚举循环次数
            {
                int le=(j-1)*i+1;
                int re=j*i;
                for(register int k=le;k<=re;k++)//判断循环节
                    if(a[k]!=a[k-i])
                    {
                        flag=0;
                        break;
                    }
                if(flag)//循环成立枚举A,B分界点统计次数
                {
                    for(register int k=1;k<i;k++)
                        if(jia[k]<=jic[re+1])
                            ans++;
                }
                else
                    break;//循环不成立退出
            }
        }
        printf("%lld\n",ans);
        continue;
    }
    return 0;
}

下面考虑优化时间复杂度。

前置知识

• 字符串hash

没了

我们可以想到，时间主要浪费在以下两点：

• 在查找循环节时暴力匹配显然不是一个明智之举
• 查找\(A\),\(B\)分界时单一操作重复多次。

那么考虑优化：

显然,一个字符串出现奇数次的字符的数量\(\le\) \(26\) 废话，那么可以

维护一个类似前缀和的东西\(R\)(\(i\),\(j\))表示从\(1-i\)奇数次的字符的数量满足\(\le\) \(j\)的位置，用\(L\)(\(i\))表示从\(i-n\)奇数次的字符的数量。

于是，对可成立的A+B字符串判断复杂度变成了预处理\(O\)(\(27n\)),查询\(O\)(\(1\))。

其次，可以用字符串哈希或KMP判循环节，将判循环节复杂度优化为调和级数级即\(O\)(\(n\) \(\ln\) \(n\))。

加上这两个优化后复杂度大概在\(O( T(27n+n \ln n) )\)。

喜闻乐见的 Code ：

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define N (1<<20)+50
using namespace std;

LL ans;
int t,len;
char a[N];
int sm[N][27],sum[N];//分别对应题解中的L(i,j),R(i)
ULL Hash[N],jc[N],p=13331;//hash采取p进制，不过最好用双模数
//因为我太懒了，用了单模数哈希QAQ
inline int qr()//平平无奇的快读
{
    char a=0;int x=0,w=1;
    while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
    while(a<='9'&&a>='0'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
    return x*w;
}

inline bool check(int l,int r,int L,int R)//字符串哈希判断相等
{
    ULL hash1=(Hash[r]-Hash[l-1]*jc[r-l+1]);
    ULL hash2=(Hash[R]-Hash[L-1]*jc[R-L+1]);
    if(hash1==hash2)
        return 1;
    return 0;
}

int main()
{
    t=qr();
    jc[0]=1;
    for(register int i=1;i<=(1<<20)+5;i++)
        jc[i]=jc[i-1]*p;//处理p^i
    while(t--)
    {
        scanf("%s",(a+1));
        len=strlen(a+1);
        ans=0;
        int opk[27]={},val=0;
        for(register int i=1;i<=len;i++)
            Hash[i]=(Hash[i-1]*p+a[i]);//计算hash值
        for(register int i=1;i<=len;i++)//预处理L(i,j)
        {
            for(register int j=0;j<=26;j++)
                sm[i][j]=sm[i-1][j];//首先继承i-1时的前缀和
            opk[(int)(a[i]-'a')+1]++;
            opk[(int)(a[i]-'a')+1]&1?val++:val--;
            sm[i][val]++;//加上统计的最新答案
        }//这时sm(i,j)表示的仅为 1~i   中出现奇数次的字符数量=j的数量，于是需要再做一下前缀和
        for(register int i=1;i<=len;i++)
            for(register int j=1;j<=26;j++)
                sm[i][j]+=sm[i][j-1];//现在sm(i,j)表示的就是 1~i 中出现奇数次的字符数量<=j的数量了
        val=0;
        memset(opk,0,sizeof(opk));
        for(register int i=len;i>=1;i--)//预处理R(i,j)
        {
            opk[(int)(a[i]-'a')+1]++;
            opk[(int)(a[i]-'a')+1]&1?val++:val--;
            sum[i]=val;
        }//没啥可说的
        for(register int i=2;i<len;i++)
            for(register int j=1;j*i<len;j++)//开始判循环节
            {
                int re=j*i+1;
                if(check(1,i,i*(j-1)+1,j*i))//如果循环节成立
                    ans+=sm[i-1][sum[re]];//统计答案
                else
                    break;//不成立直接退出即可
            }
        printf("%lld\n",ans);
        continue;
    }
    return 0;
}

Update:

发现\(R\)(\(i\),\(j\))可以边进行计算边求，优化了一些常数(不开O2有96分，C++11就过了)，代码如下：

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define N (1<<20)+50
using namespace std;

LL ans;
int t,len;
char a[N];
int sm[27],sum[N];//分别对应题解中的L(i,j),R(i)
ULL Hash[N],jc[N],p=13331;//hash采取p进制，不过最好用双模数
//因为我太懒了，用了单模数哈希QAQ
inline int qr()//平平无奇的快读
{
    char a=0;int x=0,w=1;
    while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
    while(a<='9'&&a>='0'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
    return x*w;
}

inline bool check(int l,int r,int L,int R)//字符串哈希判断相等
{
    ULL hash1=(Hash[r]-Hash[l-1]*jc[r-l+1]);
    ULL hash2=(Hash[R]-Hash[L-1]*jc[R-L+1]);
    if(hash1==hash2)
        return 1;
    return 0;
}

int main()
{
    t=qr();
    jc[0]=1;
    for(register int i=1;i<=(1<<20)+5;i++)
        jc[i]=jc[i-1]*p;//处理p^i
    while(t--)
    {
        scanf("%s",(a+1));
        len=strlen(a+1);
        ans=0;
        int opk[27]={},val=0;
        for(register int i=1;i<=len;i++)
            Hash[i]=(Hash[i-1]*p+a[i]);//计算hash值
        val=0;
        for(register int i=len;i>=1;i--)//预处理R(i,j)
        {
            opk[(int)(a[i]-'a')+1]++;
            opk[(int)(a[i]-'a')+1]&1?val++:val--;
            sum[i]=val;
        }//没啥可说的
        val=0;
        memset(sm,0,sizeof(sm));
        memset(opk,0,sizeof(opk));
        for(register int i=2;i<len;i++)
        {
            opk[(int)(a[i-1]-'a')+1]++;
            opk[(int)(a[i-1]-'a')+1]&1?val++:val--;
            for(register int j=val;j<=26;j++)
                sm[j]++;//求R(i,j)
            for(register int j=1;j*i<len;j++)//开始判循环节
            {
                int re=j*i+1;
                if(check(1,i,i*(j-1)+1,j*i))//如果循环节成立
                    ans+=sm[sum[re]];//统计答案
                else
                    break;//不成立直接退出即可
            }
        }

        printf("%lld\n",ans);
        continue;
    }
    return 0;
}