Luogu P2375 [NOI2014]动物园

题目描述

https://www.luogu.com.cn/problem/P2375

Solution

能够发现实质上对于 $nxt$ 树上每个点统计一下到根的节点数量，唯一需要注意的是对 $border$ 有长度要求

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1000010
#define ll long long 
using namespace std;

const int p = 1000000007;

int n; 

char s[maxn];

int nxt[maxn], dep[maxn]; ll ans; 
void init_nxt(char *s) {
    nxt[1] = 0; dep[1] = 1; int k = 0, t = 0, d = 0, n = strlen(s + 1); 
    for (int i = 2; i <= n; ++i) {
        while (k && s[i] != s[k + 1]) k = nxt[k];
        if (s[i] == s[k + 1]) ++k;
        nxt[i] = k; dep[i] = dep[k] + 1; 
        
        while (t && s[i] != s[t + 1]) t = nxt[t];
        if (s[i] == s[t + 1]) ++t;
        while (t && t > i / 2) t = nxt[t];
        ans = ans * (dep[t] + 1) % p; 
    }
} 

void work() {
    scanf("%s", s + 1); ans = 1; 
    init_nxt(s); cout << ans << endl; 
} 

int main() {
    int T; cin >> T;
    while (T--) work();
    return 0;
}