[题解]第十一届北航程序设计竞赛预赛——L.偶回文串

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 #define MaxLen 100020
 8 
 9 typedef long long llt;
10 typedef unsigned long long ullt;
11 
12 llt a[MaxLen], Sum[MaxLen];
13 char s[MaxLen];
14 bool vis[30];
15 
16 int main()
17 {
18     //freopen("L.in", "r", stdin);
19     llt i, Len, pos;
20     ullt tmp, ans;
21     while(scanf("%s", s) != EOF)
22     {
23         memset(vis, false, sizeof(vis));
24         Len = strlen(s);
25         Sum[0] = 0;
26         for(i = 1; i <= Len; i++)
27         {
28             tmp = s[i - 1] - ‘a‘;
29             if(vis[tmp])
30             {
31                 a[i] = -(1 << tmp);
32                 vis[tmp] = false;
33             }
34             else
35             {
36                 a[i] = 1 << tmp;
37                 vis[tmp] = true;
38             }
39             Sum[i] = Sum[i - 1] + a[i];
40         }
41         sort(Sum, Sum + Len + 1);
42         ans = 0;
43         for(i = 0; i <= Len; i++)
44         {
45             if(i == 0)
46             {
47                 pos = 0;
48                 continue;
49             }
50             if(Sum[i] != Sum[pos])
51             {
52                 tmp = i - pos;
53                 ans += tmp * (tmp - 1) / 2;
54                 pos = i;
55             }
56         }
57         tmp = i - pos;
58         ans += tmp * (tmp - 1) / 2;
59         //ans += (i - pos) * (i - pos - 1) / 2;
60         //printf("%lld\n", ans);
61         cout << ans << endl;
62     }
63     return 0;
64 }