首先假设内存足够大的话可以用f[i]表示i这个状态出现了多少次，状态是指异或前缀和，那么根据题意，当且只有在i==0或者二进制表示下只有一个1的情况下是合法状态，所以每加一个字符，就更新当前前缀和，又由于A^B==C->A^C==B
那么可以预处理出所有合法状态，然后分别和当前状态异或后得到需要的状态，加入答案。
但是内存不够，不能用数组，amp貌似是一个不错的选择，呵呵，又T又mle，那么hash好了，呵呵，冲突太多，所以正解是用一个链表来处理所有的冲突，汗。。。
然后到底hash的时候取模多少呢？好像只要是一个不爆内存的数就好了，呵呵，卡long long取模，解决办法是选8388607因为它的二进制数是11111111111111111111111就可以用&来代替%了，嗯，我服
但是代码并不长
#include<cstdio> #include<cstring> #include<iostream> #define Mod 8388607 #define maxn 3*100021 using namespace std; typedef long long LL; int head[Mod+4],n,tot=1; LL pre[53],ans; char s[maxn]; inline int Q(char c){return c>='a'&&c<='z' ? c-'a'+27 : c-'A'+1;} struct edge{LL x;int next,cnt;}e[maxn]; void ins(LL x){ int y=x&Mod; for(int i=head[y];i;i=e[i].next)if(e[i].x==x){ e[i].cnt++;return; }e[tot].x=x,e[tot].cnt=1,e[tot].next=head[y]; head[y]=tot++; } int query(LL x){ int y=x&Mod; for(int i=head[y];i;i=e[i].next)if(e[i].x==x)return e[i].cnt; return 0; } int main(){ scanf("%d%s",&n,s+1);ins(0); for(int i=1;i<=52;i++)pre[i]=1ll<<i;LL sum=0; for(int x,i=1;i<=n;i++){ x=Q(s[i]);sum^=pre[x]; for(int i=0;i<=52;i++) ans+=query(sum^pre[i]); ins(sum); } cout<<ans; return 0; }
