C++14(g++5.4) 解法, 执行用时: 191ms, 内存消耗: 528K, 提交时间: 2020-09-29 15:44:28

#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
ll t,n,nex[5007];
string s,s2;
void kmp(string s){
	ll len=s.length();
	ll l=0,r=1;
	nex[l]=-1;
	while(r<len){
		if(l==-1||s[l]==s[r]){
			l++;
			r++;
			nex[r]=l;
		}
		else l=nex[l];
	}
}
int main(){
	scanf("%lld",&t);
	while(t--){
		cin>>s;
		n=s.length();
		s+=s;
		ll ans=0;
		for(ll j=1;j<=n;j++){
			s2="";
			for(ll i=n-j;i<n;i++){
				s2+=s[i];
			}
			kmp(s2);
			ll l=0,r=0;
			while(r<n){
				if(l==-1||s2[l]==s[r]){
					l++;
					r++;
					ans^=(r-l)*l*l*(j-l);
					while(l==s2.length())l=nex[l];
				}
				else l=nex[l];
			}
		}
		printf("%lld\n",ans);
	}
}

C++(clang++11) 解法, 执行用时: 168ms, 内存消耗: 384K, 提交时间: 2020-10-24 00:24:47

#include<bits/stdc++.h>
using namespace std;
int T,n,m,f[2009];
long long ans;
char s[2009];
void work(char *c){
	m=strlen(c+1);
	for(int i=1,j=0;i<=m;f[++i]=++j){
		while(c[i]!=c[j]&&j)j=f[j];
	}
	for(int i=1,j=1;i<=n;++i,++j){
		while(s[i]!=c[j]&&j)j=f[j];
		ans=ans^(1ll*j*j*(m-j)*(i-j));
		
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		ans=0;
		scanf("%s",s+1);
		n=strlen(s+1);
		for(int i=1;i<=n;++i){
			work(s+i-1);
		}
		printf("%lld\n",ans);
	}
	return 0;
}