花海漫步 NOI模拟题

时间：2023-03-09 07:33:39
花海漫步 NOI模拟题

题目好像难以看懂？

题目大意

给出一个字符串\(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 <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

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;

}

相关文章