题目链接：hdu 4909 String

题目大意：给定一个字符串，由小写字母组成，最多包含一个问号，问号可以表示空或者任意一个字母。问有多少个子串，字母出现的次数均为偶数。

解题思路：因为最多又26个字母，对应每个字母的奇数情况用1表示，偶数情况用0.将一个前缀串表示成一个二进制数。然后对于每种相同的数s，任选两个即为一种可行子串(组合数学). 接着对于有问号的情况枚举一下问号替代的字符，然后对于问号后面的状态都要再加上一个该字符。这时计算个数时就要将前后分开讨论了。
这题交C++，结果卡FST了，觉得很不科学，加排序复杂度才o(nlogn), 然后叫G++就过了,不过开别人好像是开了一个1<<26的数组计算个数，空间限的也太松了。

#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef int ll; const int maxn = 20005; int n, num[maxn], s[maxn]; char str[maxn]; ll solve () { int tmp = num[0] = 0; for (int i = 1; i <= n; i++) { if (str[i] != '?') tmp ^= (1<<(str[i]-'a')); s[i] = num[i] = tmp; } ll ret = 0; sort(num, num + n + 1); int mv = 0; while (mv <= n) { int p = 0; while (p + mv <= n && num[p+mv] == num[mv]) p++; ret += p * (p-1) / 2; mv += p; } return ret; } int a[maxn], b[maxn]; ll handle (int x, int pos) { int A = pos, B = n + 1 - pos; for (int i = 0; i < pos; i++) a[i] = s[i]; for (int i = pos; i <= n; i++) b[i-pos] = s[i]^(1<
      
        b[mvb]) mvb++; else if (a[mva] < b[mvb]) mva++; else { int i = 0, j = 0; while (i + mva < A && a[i+mva] == a[mva]) i++; while (j + mvb < B && b[j+mvb] == b[mvb]) j++; ret += i * j; mva += i; mvb += j; } } return ret; } int main () { int cas; scanf("%d", &cas); while (cas--) { scanf("%s", str+1); n = strlen(str+1); int pos = -1; for (int i = 1; i <= n; i++) { if (str[i] == '?') { pos = i; break; } } ll ans = solve(); if (pos != -1) { for (int i = 0; i + 'a' <= 'z'; i++) ans += handle(i, pos); } printf("%d\n", ans); } return 0; }