【LOJ】#2065. 「SDOI2016」模式字符串

题解

按秩合并怎么清数组对我来说真是世纪性难题

我们很熟练地想到点分，如果我们认为某个点到重心是正着读的，由于它的深度固定，它的串也是固定的，我们只要预处理出所有长度正着重复的串，反着重复的串，和它们的哈希值，遍历树的时候只需要记录一下路径字符串的哈希值，比对一下看是否合法就行

为了快一点可以按深度合并每棵子树

代码

#include <bits/stdc++.h>

#define enter putchar('\n')

#define space putchar(' ')

#define pii pair<int,int>

#define fi first

#define se second

#define mp make_pair

#define MAXN 1000005

#define mo 999999137

#define pb push_back

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 + c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

char s[MAXN],str1[MAXN],str2[MAXN],s1[MAXN],s2[MAXN];

int e[MAXN],h1[MAXN],h2[MAXN];

struct node {

    int to,next;

}E[MAXN * 2];

int head[MAXN],sumE,N,M;

int que[MAXN],ql,qr,fa[MAXN],siz[MAXN],son[MAXN],H[MAXN],dep[MAXN];

int t1[MAXN],t2[MAXN],sum1[MAXN],sum2[MAXN];

int64 ans;

bool vis[MAXN];

vector<pii > ver;

void add(int u,int v) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    head[u] = sumE;

}

int mul(int a,int b) {

    return 1LL * a * b % mo;

}

int inc(int a,int b) {

    return a + b >= mo ? a + b - mo : a + b;

}

void Init() {

    memset(head,0,sizeof(head));sumE = 0;

    memset(vis,0,sizeof(vis));ans = 0;

    read(N);read(M);

    scanf("%s",s + 1);

    int u,v;

    for(int i = 1 ; i < N ; ++i) {

        read(u);read(v);

        add(u,v);add(v,u);

    }

    scanf("%s",str1 + 1);

    for(int i = 1 ; i <= N ; ++i) {

        s1[i] = str1[(i - 1) % M + 1];

    }

    memcpy(str2,str1,sizeof(str1));

    reverse(str2 + 1,str2 + M + 1);

    for(int i = 1 ; i <= N ; ++i) {

        s2[i] = str2[(i - 1) % M + 1];

    }

    for(int i = 1 ; i <= N ; ++i) {

        h1[i] = inc(mul(e[i - 1],s1[i] - 'A' + 1),h1[i - 1]);

        h2[i] = inc(mul(e[i - 1],s2[i] - 'A' + 1),h2[i - 1]);

    }

}

int CalcG(int st) {

    fa[st] = 0;que[ql = qr = 1] = st;

    while(ql <= qr) {

        int u = que[ql++];siz[u] = 1;son[u] = 0;

        for(int i = head[u] ; i ; i = E[i].next) {

            int v = E[i].to;

            if(!vis[v] && v != fa[u]) {

                que[++qr] = v;

                fa[v] = u;

            }

        }

    }

    int res = que[qr];

    for(int i = qr ; i >= 1 ; --i) {

        int u = que[i];

        if(son[u] < qr - siz[u]) son[u] = qr - siz[u];

        if(fa[u]) {

            siz[fa[u]] += siz[u];

            son[fa[u]] = max(son[fa[u]],siz[u]);

        }

        if(son[u] < son[res]) res = u;

    }

    return res;

}

void Calc(int st) {

    que[ql = qr = 1] = st;H[st] = s[st] - 'A' + 1;dep[st] = 1;

    fa[st] = 0;

    while(ql <= qr) {

        int u = que[ql++];

        for(int i = head[u] ; i ; i = E[i].next) {

            int v = E[i].to;

            if(v != fa[u] && !vis[v]) {

                fa[v] = u;

                H[v] = inc(mul(H[u],e[1]),s[v] - 'A' + 1);

                dep[v] = dep[u] + 1;

                que[++qr] = v;

            }

        }

    }

    for(int i = 1 ; i <= qr ; ++i) {

        int u = que[i];

        if(H[u] == h1[dep[u]]) t1[dep[u] % M]++;

        if(H[u] == h2[dep[u]]) t2[dep[u] % M]++;

    }

}

int Get_Dep(int u,int fa) {

    int res = 1;

    for(int i = head[u] ; i ; i = E[i].next) {

        int v = E[i].to;

        if(!vis[v] && v != fa) {

            res = max(res,1 + Get_Dep(v,u));

        }

    }

    return res;

}

void dfs(int u) {

    int G = CalcG(u);

    vis[G] = 1;

    ver.clear();

    H[G] = 0;

    for(int i = head[G] ; i ; i = E[i].next) {

        int v = E[i].to;

        if(!vis[v]) ver.pb(mp(Get_Dep(v,G),v));

    }

    sort(ver.begin(),ver.end());

    int siz = ver.size();

    int t = min(ver[siz - 1].fi,M);

    for(int i = 0 ; i <= t ; ++i) sum1[i] = sum2[i] = 0;

    t = 0;sum1[0] = sum2[0] = 1;

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

        pii p = ver[i];

        for(int j = 0 ; j <= p.fi ; ++j) t1[j] = t2[j] = 0;

        Calc(p.se);

        for(int j = 0 ; j <= t ; ++j) {

            if(M - 1 - j > p.fi) continue;

            if(s[G] == str1[j + 1]) ans = inc(ans,mul(sum1[j],t2[M - 1 - j]));

            if(s[G] == str2[j + 1]) ans = inc(ans,mul(sum2[j],t1[M - 1 - j]));

        }

        for(int j = 0 ; j <= p.fi ; ++j) {sum1[j] += t1[j];sum2[j] += t2[j];}

        t = min(M - 1,p.fi);

    }

    for(int i = head[G] ; i ; i = E[i].next) {

        int v = E[i].to;

        if(!vis[v]) dfs(v);

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    int T;

    read(T);

    e[0] = 1;

    for(int i = 1 ; i <= 1000000 ; ++i) e[i] = 1LL * e[i - 1] * 47 % mo;

    while(T--) {

        Init();

        dfs(1);

        out(ans);enter;

    }

    return 0;

}

巴特西

【LOJ】#2065. 「SDOI2016」模式字符串

题解

代码

最新文章

热门文章