bzoj 2160: 拉拉队排练 (回文自动机+快速幂)

Nov 14, 2017 · 2 min read · 回文自动机快速幂

2160: 拉拉队排练

Time Limit: 10 Sec Memory Limit: 259 MB Submit: 1938 Solved: 743 [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个测试点，数据范围满足：

思路：

直接PAM.

需要注意的是，PAM构建之后，再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

/* ***********************************************
Author :111qqz
Created Time :2017年11月14日 星期二 19时05分14秒
File Name :2160.cpp
************************************************ */

#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const LL mod = 19930726;
const int N=1E6+7;
LL k;
int n;
char S[N];
struct PAM
{
    int fail;
    LL cnt,len;
    int nxt[26];
}st[N];
int now,sz;
int Right[N],Left[N]; 
void pam_init()
{
    ms(st,0);
    st[0].fail = st[1].fail = 1;
    st[1].len = -1;
    sz = 1;
}
void extend(int c,int pos)  //忘记加*S这个参数了。。。以至于没有真正反着做orz
{
    int p = now;
    while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
    if (!st[p].nxt[c]){
    int np=++sz,q=st[p].fail;
    st[np].len=st[p].len+2;
    while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
    st[np].fail=st[q].nxt[c];
    st[p].nxt[c] = np;
    }
    now=st[p].nxt[c];
    st[now].cnt++;
}
LL ksm(LL a,LL b)
{
    LL res = 1;
    while (b>0)
    {
    if (b&1) res = res * a % mod;
    b = b >> 1LL;
    a = a * a % mod;
    }
    return res;
}
pair<LL,LL>group[N];
LL solve()
{
   // puts("fuck");
    for ( int i = sz ; i >= 2 ; i--) st[st[i].fail].cnt += st[i].cnt; //这才是真正的cnt
    LL ret = 1;
    int tot = 0 ;
    LL sum = 0;
    for ( int i = 2 ; i <= sz ; i++) if (st[i].len%2==1)
    {
    group[++tot]=MP(st[i].len,st[i].cnt);//升序排列
    sum = sum + st[i].cnt;
    }
    if (sum<k) return -1;
    sort(group+1,group+tot+1); // 1.. sz-1
//    for ( int i = 1 ; i <= sz-1 ; i++) printf("[len:cnt]:[%d,%d]\n",group[i].fst,group[i].sec);
    int id = tot;
    while (k>0&&id>=1)
    {
//  printf("K:%lld id:%d\n",k,id);
    if (k>=group[id].sec) 
    {
        k-=group[id].sec;
        LL tmp = ksm(group[id].fst,group[id].sec);
        ret = ret * tmp % mod;
        id--;
    }else
    {
        LL tmp = ksm(group[id].fst,k);
        ret = ret * tmp % mod;
        k = 0 ;
        id--;
    }
    }
    return ret;
}   
int main()
{
    #ifndef  ONLINE_JUDGE 
//  freopen("./in.txt","r",stdin);
  #endif
    scanf("%d %lld",&n,&k);
    scanf("%s",S+1);
    pam_init();
    for ( int i = 1 ,_=strlen(S+1); i <= _ ; i++) extend(S[i]-'a',i);
    LL ans = solve();
    cout<<ans<<endl;


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}