ACM-ICPC 2018 Nanjing Division Network Game I.Skr (Hypertext Automated Machine)

计蒜客开开禁, I hang the script that cracks the webpage limit can be copied but not very good-looking, I will not post the title. The

topic is to give a string of numbers and find the sum of the palindrome substrings whose nature is different.

I didn’t see the “different nature” at the beginning. I wanted to run the horse-drawn car + Sam, and read the street again after reading the question.

Later I learned that it was the title of the palindrome tree.

comes with a heavy weight in the process of building the palindrome, so you only need to run it once to record the answer.

奇 根下 directly connected nodes represent a single character palindrome, the other is to add the same character on both sides, use this rule to generate a digital summation just fine.

ac码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2000005;
const int mod = 1000000007;
char s[maxn];

ll modPow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) {
            ans = (ans * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}


struct Pam {
    int next[maxn << 1][9];
    int fail[maxn << 1];
    int len[maxn << 1];
    // Record numberll num[maxn <<1];
    ll ans;
    int S[maxn << 1];
    int last, n, p;

    int newNode(int l) {
        memset(next[p], 0, sizeof(next[p]));
        len[p] = l;
        return p++;
    }

    void init() {
        n = last = p = 0;
        newNode(0);
        newNode(-1);
        S[n] = -1;
        fail[0] = 1;
    }

    int getFail(int x) {
        while(S[n - len[x] - 1] != S[n]) {
            x = fail[x];
        }
        return x;
    }

    void add(int c) {
        S[++n] = c;
        int cur = getFail(last);
        if(!next[cur][c]) {
            int now = newNode(len[cur] + 2);
            fail[now] = next[getFail(fail[cur])][c];
            next[cur][c] = now;
            // len[cur] = -1, is a palindrome consisting of a single character, special judgment
            if(len[cur] == -1) {
                num[now] = c;
            } else {
                num[now] = (((num[cur] * 10) % mod + c) % mod + (c * modPow(10, len[now] - 1)) % mod) % mod;
            }
            ans = (ans + num[now]) % mod;
        }
        last = next[cur][c];
    }

    void solve() {
        init();
        for(int i = 0, len = strlen(s); i < len; i++) {
            add(s[i] - '0');
        }
        printf("%lld\n", ans);
    }

} pam;

int main() {
    scanf("%s", s);
    pam.solve();
    return 0;
}