题目好像难以看懂？
题目大意
给出一个字符串\(S\)，统计满足以下条件的\((i,j,p,q)\)的数量。
- \(i \leq j, p \leq q\)
- \(S[i..j],S[p..q]\)是回文串
- \(i < p\)或(\(i=p\)且\(j <q\))
- \(p \leq j\)
算法
实在没懂硬求的算法，lyw lzhOrz。
我们来愉快地求补集吧：
全集很好求，接下来，枚举\(j\)，我们可以求出满足\(S[i..j]\)的\(i\)的数量\(x\)，然后减去\(p > j\)的\(S[p..q]\)的数量乘上\(x\)。
问题是如何求出满足\(S[i..j]\)的\(i\)的数量，这个直接套用回文树的做法即可。
\(p > j\)的\(S[p..q]\)的数量求法同理，只要加上一个部分和即可。
不过好像回文树还没有普及，事实上可以用Manacher算法求出的东西来达到同样的效果。
然后我就想了，既然Manacher在该问题中能达到回文树的效果，那么回文树能不能算出Manacher算出的东西呢？？？？？？？
代码
#include#include #include #include using namespace std; const int MAXN = (int) 2e6 + 3;const int MOD = (int) 1e9 + 7; typedef long long i64; int n;char str[MAXN]; struct Node { Node* s[26]; Node* fail; int len, cnt;}; Node memory[MAXN];Node* curMem = memory;Node* root0;Node* root1; Node* getFail(Node* x, int i) { while (i == x->len || str[i] != str[i - x->len - 1]) x = x->fail; return x;} void solve(int ans[]) { Node* cur = root1; for (int i = 0; i < n; i ++) { int p = str[i] - 'a'; cur = getFail(cur, i); if (! cur->s[p]) { Node* x = curMem ++; x->len = cur->len + 2; cur->s[p] = x; if (cur == root1) x->fail = root0; else x->fail = getFail(cur->fail, i)->s[p]; x->cnt = x->fail->cnt + 1; } cur = cur->s[p]; ans[i] = cur->cnt; }} int main() {#ifdef debug freopen("input.txt", "r", stdin);#endif scanf("%d\n", &n); scanf("%s", str); static int A[MAXN], B[MAXN]; root0 = curMem ++; root1 = curMem ++; root1->len = -1; root0->fail = root1; solve(A); reverse(str, str + n); solve(B); reverse(B, B + n); for (int i = n - 1; i >= 0; i --) B[i] = (B[i] + B[i + 1]) % MOD; i64 ans = (i64) B[0] * (B[0] - 1) % MOD * 500000004 % MOD; for (int i = 0; i + 1 < n; i ++) ans = (ans - (i64) A[i] * B[i + 1]) % MOD; if (ans < 0) ans += MOD; cout << ans << endl; return 0;}