注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2160]拉拉队排练  

2015-05-14 14:56:55|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2160: 拉拉队排练

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 484  Solved: 188
[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 【样例说明】 和谐小群体女生所拿牌子上写的字母从左到右按照女生个数降序排序后为ababa, aba, aba, bab, a, a, a, b, b,前三个长度的乘积为。

HINT

总共20个测试点,数据范围满足: 

Solution

求出回文自动机以后,就是沿着-1节点的子树进行DP,沿fail树转移就好了。于是算答案的时候快速幂搞搞就没了。
一直Wa是我默认了最长回文子串为奇数,还有-1没判。要加强静查。

Code

/**************************************************************
    Problem: 2160
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:528 ms
    Memory:122876 kb
****************************************************************/
 
#include<cstdio>
#define P 19930726
#define N 1000010
typedef long long ll;
int tot,las,now,len[N],ch[N][26],fail[N],cnt[N],n,i,j,l;ll ans,k,pow[N];char s[N];
ll power(ll t,ll k){
    if(t==1||k==0)return 1;ll f=1;
    for(;k;k>>=1,t=t*t%P)if(k&1)f=f*t%P;
    return f;
}
int nn(int L){len[tot]=L;l<L?l=L:1;return tot++;}
int gf(int x,int n){
    while(s[n-1-len[x]]!=s[n])x=fail[x];
    return x;
}
int main(){
    scanf("%d%lld%s",&n,&k,s+1);nn(0),nn(-1);fail[0]=1;s[0]=-1;
    for(i=1;i<=n;i++){
        s[i]-='a';las=gf(las,i);
        if(!ch[las][s[i]]){
            now=nn(len[las]+2);
            fail[now]=ch[gf(fail[las],i)][s[i]];
            ch[las][s[i]]=now;
        }
        cnt[las=ch[las][s[i]]]++;
    }
    for(i=tot;i>1;i--)cnt[fail[i]]+=cnt[i],len[i]&1?pow[len[i]]+=cnt[i]:1;
    for(ans=1,~l&1?l--:1;l>=1&&k>0;l-=2)pow[l]>k?pow[l]=k:1,ans=ans*power(l,pow[l])%P,k-=pow[l];
    if(k)puts("-1");else printf("%lld\n",ans);
}
  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018