C++(g++ 7.5.0) 解法, 执行用时: 231ms, 内存消耗: 5544K, 提交时间: 2023-08-04 18:03:21

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = (1 << 20) + 5;
char s[MAXN];
int n, z[MAXN];
int before[30], after[30];
int pre, suf, all;
int c[30];

inline int lbt(int x) {
    return x & -x;
}

void update(int x) {
    while (x <= 27) {
        c[x]++;
        x += lbt(x);
    }
}

int sum(int x) {
    int r = 0;
    while (x > 0) {
        r += c[x];
        x -= lbt(x);
    }
    return r;
}
void Z() {
    z[0] = n;
    int now = 0;
    while (now + 1 < n && s[now] == s[now + 1]) {
        now++;
    }
    z[1] = now;
    int p0 = 1;
    for (int i = 2; i < n; ++i) {
        if (i + z[i - p0] < p0 + z[p0]) {
            z[i] = z[i - p0];
        } else {
            now = p0 + z[p0] - i;
            now = max(now, 0);
            while (now + i < n && s[now] == s[now + i]) {
                now++;
            }
            z[i] = now;
            p0 = i;
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> s;
        n = strlen(s);
        memset(before, 0, sizeof(before));
        memset(after, 0, sizeof(after));
        memset(c, 0, sizeof(c));
        all = pre = suf = 0;
        Z();
        for (int i = 0; i < n; ++i) {
            if (i + z[i] == n) z[i]--;
        }
        for (int i = 0; i < n; ++i) {
            after[s[i] - 'a']++;
        }
        for (int i = 0; i < 26; ++i) {
            if (after[i] & 1) {
                all++;
            }
        }
        suf = all;
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            if (after[s[i] - 'a'] & 1) {
                suf--;
            } else {
                suf++;
            }
            after[s[i] - 'a']--;
            if (before[s[i] - 'a'] & 1) {
                pre--;
            } else {
                pre++;
            }
            before[s[i] - 'a']++;
            if (i != 0 && i != n - 1) {
                int t = z[i + 1] / (i + 1) + 1;
                ans += 1LL * (t / 2) * sum(all + 1) + 1LL * (t - t / 2) * sum(suf + 1);
            }
            update(pre + 1);
        }
        cout << ans << endl;
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 417ms, 内存消耗: 11704K, 提交时间: 2021-04-11 11:41:34

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N (1<<20)+5
#define mo1 1000000007
#define mo2 19260817
#define ll long long
#define lowbit(x) x&(-x)
#define I inline
#define ull unsigned long long
using namespace std;
ll tree[27];
short sum[N],js[27],qz;
ull hx1[N],hx2[N];
ull mi1,mi2,g1;
char c[N];
int main()
{
	int cs;
	scanf("%d\n",&cs);
	while (cs--)
	{  
		scanf("%s\n",c+1);
		int n=strlen(c+1);memset(tree,0,sizeof(tree));memset(js,0,sizeof(js));
		ll ans=0;
		sum[n+1]=0;
		for ( int i=1;i<=n;i++) hx1[i]=hx1[i-1]*27+(c[i]-'a');
		for ( int i=n;i>=1;i--) 
		{  
			js[c[i]-'a']^=1;	
			sum[i]=sum[i+1]+(js[c[i]-'a']%2?1:-1);
		} memset(js,0,sizeof(js));
		js[0]=0,js[c[1]-'a']=1;
		for ( int i=1;i<=26;i++) tree[i]++;
		qz=1;mi1=mi2=27;
		for ( int i=2;i<=n-1;i++)
		{   
			g1=0;
			mi1=mi1*27;
			for ( int j=1;j<=n/i;j++)
			{   
				g1=g1*mi1+hx1[i];
				if (j*i>=n) break;
				if (g1==hx1[j*i])ans+=tree[sum[j*i+1]];
				else break;
			}
			js[c[i]-'a']^=1;
			qz+=(!(js[c[i]-'a']&1))?-1:1;
			for ( int j=qz;j<=26;j++) tree[j]++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}