ACM-ICPC 2018 南京赛区网络预赛 I. Skr【回文树】

题目分析，首先这个题是一个经典的求字符串中不同的回文子串的题，那么这个题我们可以用回文树来做，具体回文树的实现过程去看其他的博客，这里就不再赘述。
那么我们通过回文树可以得到什么呢？ 可以在线性的时间复杂度内得到2棵树，一棵树代表的是偶数回文串，另一棵树代表的是奇数回文串。
举例
我们以 0为根节点的作为偶回文 1为根节点的作为奇数回文串
那么如果我们有一个串 1121 那么我们就会得到

并且我们还会得到每一个结点所代表的回文串的长度，保存在len[i]中；
然后我们要计算所有的数加起来，这个怎么算呢？
我们通过dfs去遍历每个结点，对于每一个结点u，我们可以通过 len[u] 来计算出这个结点的数对于答案的贡献 显然就是 (10^(len[u]-1) +1)*ch[u] 那么我们把左边的权值和右边的权值存起来，
对于当前结点的父亲节点，它的权值就应该要加上子节点 左端权值/10 和右端权值*10
这样dfs结束，我们就可以把所有的值算出来了。

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
using namespace std;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
typedef pair<int, int> PII;
ll fpow(ll n, ll k, ll p = mod) { ll r = 1; for (; k; k >>= 1) { if (k & 1) r = r * n%p; n = n * n%p; } return r; }
ll inv(ll a, ll p = mod) { return fpow(a, p - 2, p); }
const int maxn = 2e6 + 50;
const int N = 11;
ll ans;
ll pp[maxn];
int nxt[maxn][N];
int fail[maxn];
int cnt[maxn];
int num[maxn];
int len[maxn];
ll mp[maxn];
int S[maxn];
int last;
int n, p;
ll inv10;
int newnode(int l)
{
    for (int i = 0; i<N; i++) nxt[p][i] = 0;
    cnt[p] = 0;
    num[p] = 0;
    len[p] = l;
    return p++;
}
void init()
{
    p = 0;
    newnode(0);
    newnode(-1);
    last = 0;
    n = 0;
    S[n] = -1;
    fail[0] = 1;
}
int get_fail(int x)
{
    while (S[n - len[x] - 1] != S[n]) x = fail[x];
    return x;
}
void add(int c)
{
    S[++n] = c;
    int cur = get_fail(last);
    if (!nxt[cur][c])
    {
        int now = newnode(len[cur] + 2);
        fail[now] = nxt[get_fail(fail[cur])][c];
        nxt[cur][c] = now;
        num[now] = num[fail[now]] + 1;
    }
    last = nxt[cur][c];
    cnt[last]++;
    mp[last] = c;
}
void countt()
{
    for (int i = p - 1; i >= 0; --i) cnt[fail[i]] += cnt[i];
}
char ch[maxn];
ll l[maxn], r[maxn];
void dfs(int u, int fa)
{
    for (int i = 0; i <= 9; i++)
    {
        if (nxt[u][i])dfs(nxt[u][i], u);
    }
    if (u == 0 || u == 1)return;
    r[u] += 1;
    l[u] += pp[len[u] - 1];
    if (len[u] == 1) r[u] = 0;
    l[u] %= mod; r[u] %= mod;
    ans = (ans + mp[u] * (l[u] + r[u])) % mod;
    l[fa] += l[u] * inv10%mod;
    r[fa] += r[u] * 10 % mod;
}
int main()
{

    inv10 = inv(10, mod);
    pp[0] = 1;
    for (int i = 1; i <= maxn; i++) pp[i] = pp[i - 1] * 10 % mod;
    init();
    scanf("%s", ch);
    int len = strlen(ch);
    for (int i = 0; i<len; i++)
    {
        add(ch[i] - '0');
    }
    dfs(0, -1);
    dfs(1, -1);
    cout<<ans<<endl;
    return 0;
}