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
");
            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
",ans);
    }
    return 0;
}