题目链接
利用回文树求前缀后缀的回文子串数,枚举计算答案即可。
int main() {
#ifdef LOCAL
INPUT;
OUTPUT;
#endif
// scanf("%d", &n);
scanf("%s", S + 1);
n=strlen(S+1);
LL cnt = 0;
memset(R, 0, sizeof R);
for (int i = 1, l = 0, r = 0; i <= n; ++i) {
if (i <= r) R[i] = min(r - i + 1, R[l + r - i]);
while (1 <= i - R[i] && i + R[i] <= n && S[i - R[i]] == S[i + R[i]]) R[i]++;
if (i + R[i] - 1 > r) l = i - R[i] + 1, r = i + R[i] - 1;
cnt += R[i];
Start[i - R[i] + 1]++; End[i]++;
Start[i + 1]--; End[i + R[i]]--;
//printf("%d ", R[i]);
}
//puts("");
memset(R, 0, sizeof R);
for (int i = 1, l = 0, r = 0; i <= n - 1; ++i) {
if (i < r) R[i] = min(r - i, R[l + r - i - 1]);
while (1 <= i - R[i] && i + R[i] < n && S[i - R[i]] == S[i + R[i] + 1]) R[i]++;
if (i + R[i] > r) l = i - R[i] + 1, r = i + R[i];
cnt += R[i];
Start[i - R[i] + 1]++; End[i + 1]++;
Start[i + 1]--; End[i + R[i] + 1]--;
//printf("%d ", R[i]);
}
//puts("");
LL ans =0;
for (int i = 1; i <= n; ++i) Start[i] = (Start[i] + Start[i - 1]) % M;
for (int i = 1; i <= n; ++i) End[i] = (End[i] + End[i - 1]) % M;
for (int i = 1; i <= n; ++i) End[i] = (End[i] + End[i - 1]) % M;
for (int i = 1; i <= n; ++i) ans = (ans + Start[i] * End[i - 1] % M + M) % M;
cout << ans;
return 0;
}