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

45

回文树模板

#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ3884: 上帝与集合的正确用法(欧拉函数 扩展欧拉定理)

第二天, 上帝创造了一个新的元素,称作“α”。“α”被定义为“元”构成的集合。容易发现,一共有两种不同的“α”。

1362
来自专栏HansBug's Lab

1935: [Shoi2007]Tree 园丁的烦恼

1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

2958
来自专栏C语言及其他语言

[每日一题]最多约数问题(1228)

本次的题目正确率可是低到了一个境界呢!快来试试吧! 题目描述 正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如,1,2, 5...

3676
来自专栏desperate633

[编程题] 赶去公司代码

终于到周末啦!小易走在市区的街道上准备找朋友聚会,突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域,每条街道假设坐标是(X,...

722
来自专栏专知

关关的刷题日记78 – Leetcode 69. Sqrt(x)

关关的刷题日记78 – Leetcode 69. Sqrt(x) 题目 Implement int sqrt(int x). Compute and retur...

3556
来自专栏专注研发

poj-1008-玛雅历

上周末,M.A. Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳(玛雅人用于记事的工具)中,教授发现玛雅人使用了一个一年有365天的叫做Haab的历法...

1733
来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

3835
来自专栏chenjx85的技术专栏

leetcode-202-Happy Number

3177
来自专栏我的python

递归方法的理解

递归思想算是编程中比较常见但对初学者而言又有些难以理解的方法了。在leetcode上刷了几道题都用递归思想成功解决后觉得应该贯彻互联网的开源共享精神,总结一下自...

980
来自专栏数据结构与算法

1026 逃跑的拉尔夫

1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

3718

扫码关注云+社区

领取腾讯云代金券