记录编号	596464	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2020]字符串匹配	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	4.008 s
提交时间	2024-10-28 10:59:32	内存使用	15.98 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int,ll>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e6+1e5;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n;
char c[N];
ull ha[N],p[N] = {1,127};
int v[30],cnt[N],su[N];
ll ans = 0;

struct BIT{
	int c[N];
	void clear(){memset(c,0,sizeof c);}
	int lowbit(int x){return x & (-x);}
	void add(int x,int val){
		for(;x <= n + 1;x += lowbit(x))c[x] += val;
	}
	int ask(int x){
		int ans = 0;
		for(;x > 0;x -= lowbit(x))ans += c[x];
		return ans;
	}
}t;

void solve(){
	scanf("%s",c + 1);
	n = strlen(c + 1);
	for(int i = 2;i <= n;i++)p[i] = p[i-1] * 127;
	for(int i = 1;i <= n;i++)
		ha[i] = ha[i-1] * p[1] + c[i]-'a';
	memset(v,0,sizeof v);
	cnt[n + 1] = 0;
	for(int i = n;i >= 1;i--)
		if(v[c[i]-'a'])cnt[i] = cnt[i+1] - 1,v[c[i]-'a'] = 0;
		else cnt[i] = cnt[i+1] + 1,v[c[i]-'a'] = 1;
	memset(v,0,sizeof v);
	memset(su,0,sizeof su);
	t.clear();
	int s = 0;ans = 0;
	for(int i = 1;i < n;i++){
		for(int j = i;j < n;j += i)
			if(ha[i] == ha[j] - ha[j-i] * p[i])ans += t.ask(cnt[j+1] + 1);
			else break;
//		ans += su[i] * t.ask(cnt[i+1] + 1);
		//
		if(v[c[i]-'a'])s--,v[c[i]-'a'] = 0;
		else s++,v[c[i]-'a'] = 1;
		t.add(s + 1,1);
	}
	printf("%lld\n",ans);
}

int main(){
	freopen("2020string.in","r",stdin);
	freopen("2020string.out","w",stdout);
	int t = read();
	while(t--)solve();

	return 0;

}