链接

点击跳转

题解

把每个后缀拿出来，连在整个串的前面，然后kmp

代码

#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define iinf 0x3f3f3f3f #define linf (1ll<<60) #define eps 1e-8 #define maxn 1000010 #define maxe 1000010 #define cl(x) memset(x,0,sizeof(x)) #define rep(i,a,b) for(i=a;i<=b;i++) #define drep(i,a,b) for(i=a;i>=b;i--) #define em(x) emplace(x) #define emb(x) emplace_back(x) #define emf(x) emplace_front(x) #define fi first #define se second #define de(x) cerr<<#x<<" = "<<x<<endl using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll read(ll x=0) { ll c, f(1); for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f; for(;isdigit(c);c=getchar())x=x*10+c-0x30; return f*x; } struct KMP { int n, next[maxn], t[maxn]; void build(const char *r, int len) { int i, j=0; n=len; for(i=1;i<=len;i++)t[i]=r[i]; t[len+1]=0; for(i=2;i<=len;i++) { for(;j and t[j+1]!=t[i];j=next[j]); next[i] = t[j+1]==t[i]?++j:0; } } int move(int pos, int x) { for(;pos and t[pos+1]!=x;pos=next[pos]); return t[pos+1]==x ? pos+1 : 0; } }kmp; int main() { ll ans=0, T=read(); while(T--) { string s; cin>>s; string t; ll i, j, len=s.length(); ans=0; rep(i,0,len-1) { t = s.substr(i) + '|' + s; kmp.build(t.c_str()-1,t.length()); rep(j,1,len) { ll b = kmp.next[len-i+1+j], c=(len-i-b), a=(j-b); ans ^= a*b*b*c; } } cout<<ans<<endl; } return 0; }