题目链接：codeforces 17 E
这题是cf 2900的题目 ，还是上古题，其实还好
思路：先找回文串的个数，这个应该挺简单。我的方法是求一个以某字母为做端点作为回文串的L数组，在做manacher的时候差分一下在求两次前缀和就可以得到了（似乎有点麻烦）其实还好
至于如何差分：思考这样一个问题，在做manacher的时候，是不是会枚举回文中心？每次枚举结束后，是不是会得到该回文中心的最长回文半径？ 这样 假设回文中心的下标是i，最长回文半径是r,那么我们让L[i-r+1] = 1,L[i+1] = -1,是不是第一次前缀和，我们就能知道对于每一个字母，有多少个回文串是以它为左端点，，emmm这样应该好理解了，那我们再求一次前缀和呢？那是不是表示，L[i]是i左边的（包括i）所有以 1到i的位置的字母为左端点的回文串，嗯，所以L[len]就是所有回文串的数目了
那这之后呢，其实有了这个前缀和啥都好办，我们再求一个R[i]的前缀和，它的内涵和L相似，就是以当前位置为右端点的回文串数目（怎么差分应该不用我说了）。好了，我们可以用回文串总数得出所有组合，假设总数为tot ，所有组合即为(tot-1)*tot/2;再减去不重合的就行，这个不重合的算法也比较巧妙，我们枚举每个位置，R[i]*(L[len]-L[i])就是当前位置可以得到的不重合的组合数，至于为什么是这样，仔细想想就知道了（L求了两次前缀和，R只求了一次）
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 2e6+10; char s[N]; char s_new[N*2+1]; int p[N*2+1];//空间为2*n+1 时间为n ll L[N*2+1],R[N*2+1]; int m,n; const ll mod = 51123987; int Init() { int len = n; s_new[0] = '$'; s_new[1] = '#'; int j = 2; for (int i = 0; i < len; i++) { s_new[j++] = s[i]; s_new[j++] = '#'; } s_new[j] = '\0'; return j; } void Manacher() { int len = Init(); m = len; int max_len = -1; // 最长回文长度 int id; int mx = 0; for (int i = 1; i < len; i++) { if (i < mx) p[i] = min(p[2 * id - i], mx - i); else p[i] = 1; while (s_new[i - p[i]] == s_new[i + p[i]]) p[i]++; if (mx < i + p[i]) { id = i; mx = i + p[i]; } if(p[i]!=1){ L[i-p[i]+1]++; L[i+1]--; R[i]++; R[i+p[i]]--; } } } int main() { scanf("%d",&n); scanf("%s",s); Manacher(); for(int i = 1; i < m; i++){ L[i]+=L[i-1]; R[i]+=R[i-1]; } for(int i = 2; i < m; i++) L[i]+=L[i-2]; ll tot = L[m-2]; if(tot%2==0) tot=(tot/2%mod)*((tot-1)%mod)%mod; else tot = (tot%mod)*((tot-1)/2%mod)%mod; //错了几次这里，要多次取余才不会wa for(int i = 1; i < m; i++) if(s_new[i]>='a'&&s_new[i]<='z') tot = (tot-R[i]*(L[m-2]-L[i])+mod*100000LL)%mod;//担心为负数 printf("%lld\n",tot); return 0; }
