【ACM-ICPC 2018 南京赛区网络预赛 I】Skr

让你把一个字符串的所有回文子串加起来。(当做数字加起来)
求他们的和。

【题解】

回文树。
从两个根节点分别遍历整棵回文树。
按照每个节点的定义。
得到每个节点对应的数字就好。
(节点之间都有联系,很容易快速搞出来到达下一个节点的数字是什么的。
有点卡内存。一直优化才没超内存的。
后来发现,空间不用*2的。。。
$直接O(N*ALP)的空间复杂度就好$
$不用O(N*2*ALP)。。$

【代码】

#include <bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn = 2e6+10;

const int ALP = 10;

const LL MOD = 1e9+7;

LL _pow(LL x,LL y){

    LL a = 1;x%=MOD;

    while (y){

        if (y&1) a = (a*x)%MOD;

        x=(x*x)%MOD;

        y>>=1;

    }

    return a;

}

struct PAM{

    int nex[maxn][ALP];

    int fail[maxn];

    int len[maxn],root,root1;

    int s[maxn];

    int last,n,p;

    LL ans;

    int newnode(int l){

        for(int i=0;i<ALP;i++)

            nex[p][i]=0;

        len[p]=l;

        return p++;

    }

    void init(){

        ans = 0;

        p = 0;

        root = newnode(0);

        root1 = 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){

        c = c-'0';

        s[++n] = c;

        int cur = get_fail(last);

        if(!nex[cur][c]){

            int now = newnode(len[cur]+2);

            fail[now] = nex[get_fail(fail[cur])][c];

            nex[cur][c] = now;

        }

        last = nex[cur][c];

    }

    void dfs(int x,LL s,int len){

        for (int i = 0;i < 10;i++){

            if (nex[x][i]!=0){

                LL ts = s;

                int tlen = len;

                if (x==root1){

                    ts = (ts*10 + i)%MOD;

                    tlen++;

                }else if (x==root){

                    ts = (ts*10 + i)%MOD;

                    ts = (ts*10 + i)%MOD;

                    tlen+=2;

                }else{

                    ts = (ts*10 + i)%MOD;

                    tlen++;

                    ts = (ts+i*_pow(10,tlen)%MOD)%MOD;

                    tlen++;

                }

                ans = (ans+ts)%MOD;

                dfs(nex[x][i],ts,tlen);

            }

        }

    }

}pam;

string s;

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

    cin >> s;

    int len = s.size();

    pam.init();

    for(int i=0;i<len;i++){

        pam.add(s[i]);

    }

    pam.dfs(pam.root1,0,0);

    pam.dfs(pam.root,0,0);

    printf("%lld\n",pam.ans);

    return 0;

}

巴特西

【ACM-ICPC 2018 南京赛区网络预赛 I】Skr

最新文章

热门文章