HYSBZ 2160 拉拉队排练（回文树）

2160: 拉拉队排练

Time Limit: 10 Sec Memory Limit: 259 MB

Submit: 825 Solved: 324

[Submit][Status][Discuss]

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。

Input

输入为标准输入。第一行为两个正整数n和K，代表的东西在题目描述中已经叙述。接下来一行为n个字符，代表从左到右女生拿的牌子上写的字母。

Output

输出为标准输出。输出一个整数，代表题目描述中所写的乘积除以19930726的余数，如果总的和谐小群体个数小于K，输出一个整数-1。

Sample Input

5 3

ababa

Sample Output

回文树模板

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

typedef long long int LL;

const int maxn=1e6+5;

const LL mod=19930726;

char str[maxn];

LL n,k;

int cot;

LL sum;

struct _link

{

    int u[maxn];int v[maxn];

    int _next[maxn];int head[maxn];

    int tot;

    void clear()

    {

        memset(head,-1,sizeof(head));

        tot=0;

    }

    int get(int x,int y)

    {

        for(int i=head[x];i!=-1;i=_next[i])

        {

            if(u[i]==y)

                return v[i];

        }

        return 0;

    }

    void insert(int x,int y,int z)

    {

        u[tot]=y; v[tot]=z;

        _next[tot]=head[x];

        head[x]=tot++;

    }

};

struct Node

{

    int len;

    LL num;

}c[maxn];

struct Tree

{

    _link _next;

    int fail[maxn];

    int len[maxn];

    LL cnt[maxn];

    int s[maxn];

    int last;

    int p;

    int n;

    int new_node(int x)

    {

        cnt[p]=0;

        len[p]=x;

        return p++;

    }

    void init()

    {

        _next.clear();

        p=0;

        new_node(0);

        new_node(-1);

        last=0;

        n=0;

        s[0]=-1;

        fail[0]=1;

    }

    int get_fail(int x)

    {

        while(s[n-len[x]-1]!=s[n])

            x=fail[x];

        return x;

    }

    int add(int x)

    {

        x-='a';

        s[++n]=x;

        int cur=get_fail(last);

        if(!(last=_next.get(cur,x)))

        {

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

            fail[now]=_next.get(get_fail(fail[cur]),x);

            _next.insert(cur,x,now);

            last=now;

        }

        cnt[last]++;

        return 1;

    }

    void count()

    {

        for(int i=p-1;i>=0;i--)

            cnt[fail[i]]+=cnt[i];

    }

    LL fun()

    {

        count();

        cot=0;LL sum=0;

        for(int i=2;i<=p-1;i++)

        {

            if(!(len[i]&1)) continue;

            c[cot].len=len[i],c[cot++].num=cnt[i];

            sum+=cnt[i];

        }

        return sum;

    }

}tree;

int cmp(Node a,Node b)

{

    return a.len>b.len;

}

LL quick(LL n,LL x)

{

    LL sum=1;

    for(x;x;x>>=1)

    {

        if(x&1)

            sum=(sum*n)%mod;

        n=(n*n)%mod;

    }

    return sum;

}

int main()

{

    while(scanf("%lld%lld",&n,&k)!=EOF)

    {

        scanf("%s",str);

        tree.init();

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

            tree.add(str[i]);

        sum=tree.fun();

        sort(c,c+cot,cmp);

        if(sum<k)

        {

            printf("-1\n");

            continue;

        }

        LL ans=1;

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

        {

            if(k>c[i].num)

            {

                ans=(ans*quick(c[i].len,c[i].num))%mod;

                k-=c[i].num;

            }

            else

            {

                 ans=(ans*quick(c[i].len,k))%mod;

                 k=0;

            }

            if(k==0)

                break;

        }

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

    }

    return 0;

}

巴特西