记录编号	574257	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2020]字符串匹配	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	3.988 s
提交时间	2022-08-03 20:35:15	内存使用	72.14 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxn = (1 << 20) + 5;
const int maxm = 30;
const int p = 131;
typedef long long ll;
char s[maxn];
int n,sum[maxn][maxm],Hash[maxn],pw[maxn],suf[maxn];
ll ans;
void work() {
	scanf("%s",s + 1);
	n = strlen(s + 1);
	Hash[0] = 0;
	pw[0] = 1;
	int cnt[maxm] = {0};
	int cur = 0;
	//calc pre
	for(int i = 1;i <= n;++ i) {
		for(int j = 0;j < maxm;++ j)sum[i][j] = 0;
		pw[i] = pw[i - 1] * p;
		Hash[i] = Hash[i - 1] * p + s[i];
		if(cnt[s[i] - 'a'] & 1)-- cur;
		else ++ cur;
		++ cnt[s[i] - 'a'];
		sum[i][cur] = 1;
	}
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= 26;++ j) {
			sum[i][j] += sum[i][j - 1];
		}
		for(int j = 0;j <= 26;++ j) {
			sum[i][j] += sum[i - 1][j];
		}
	}
	//calc suffix
	memset(cnt , 0 , sizeof(cnt));
	suf[n + 1] = 0;
	for(int i = n;i;-- i) {
		if(cnt[s[i] - 'a'] & 1)suf[i] = suf[i + 1] - 1;
		else suf[i] = suf[i + 1] + 1;
		++ cnt[s[i] - 'a'];
	}
	ans = 0;
	for(int i = 2;i < n;++ i) {
		for(int j = i;j < n;j += i) {
			if(Hash[i] != Hash[j] - Hash[j - i] * pw[i])break ;
			ans += sum[i - 1][suf[j + 1]];
		}
	}
	printf("%lld\n",ans);
	return ;
}
int main() {
	freopen("2020string.in","r",stdin);
	freopen("2020string.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T --)work();
	return 0;
}