bzoj 2160: 拉拉队排练 (回文自动机+快速幂)
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
需要注意的是，PAM构建之后，再按照逆拓扑序更新一遍得到的cnt才是实际的cnt
需要注意的是，PAM构建之后，再按照逆拓扑序更新一遍得到的cnt才是实际的cnt
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月14日 星期二 19时05分14秒
4File Name :2160.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const LL mod = 19930726;
24const int N=1E6+7;
25LL k;
26int n;
27char S[N];
28struct PAM
29{
30 int fail;
31 LL cnt,len;
32 int nxt[26];
33}st[N];
34int now,sz;
35int Right[N],Left[N];
36void pam_init()
37{
38 ms(st,0);
39 st[0].fail = st[1].fail = 1;
40 st[1].len = -1;
41 sz = 1;
42}
43void extend(int c,int pos) //忘记加*S这个参数了。。。以至于没有真正反着做orz
44{
45 int p = now;
46 while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
47 if (!st[p].nxt[c]){
48 int np=++sz,q=st[p].fail;
49 st[np].len=st[p].len+2;
50 while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
51 st[np].fail=st[q].nxt[c];
52 st[p].nxt[c] = np;
53 }
54 now=st[p].nxt[c];
55 st[now].cnt++;
56}
57LL ksm(LL a,LL b)
58{
59 LL res = 1;
60 while (b>0)
61 {
62 if (b&1) res = res * a % mod;
63 b = b >> 1LL;
64 a = a * a % mod;
65 }
66 return res;
67}
68pair<LL,LL>group[N];
69LL solve()
70{
71 // puts("fuck");
72 for ( int i = sz ; i >= 2 ; i--) st[st[i].fail].cnt += st[i].cnt; //这才是真正的cnt
73 LL ret = 1;
74 int tot = 0 ;
75 LL sum = 0;
76 for ( int i = 2 ; i <= sz ; i++) if (st[i].len%2==1)
77 {
78 group[++tot]=MP(st[i].len,st[i].cnt);//升序排列
79 sum = sum + st[i].cnt;
80 }
81 if (sum<k) return -1;
82 sort(group+1,group+tot+1); // 1.. sz-1
83// for ( int i = 1 ; i <= sz-1 ; i++) printf("[len:cnt]:[%d,%d]\n",group[i].fst,group[i].sec);
84 int id = tot;
85 while (k>0&&id>=1)
86 {
87// printf("K:%lld id:%d\n",k,id);
88 if (k>=group[id].sec)
89 {
90 k-=group[id].sec;
91 LL tmp = ksm(group[id].fst,group[id].sec);
92 ret = ret * tmp % mod;
93 id--;
94 }else
95 {
96 LL tmp = ksm(group[id].fst,k);
97 ret = ret * tmp % mod;
98 k = 0 ;
99 id--;
100 }
101 }
102 return ret;
103}
104int main()
105{
106 #ifndef ONLINE_JUDGE
107// freopen("./in.txt","r",stdin);
108 #endif
109 scanf("%d %lld",&n,&k);
110 scanf("%s",S+1);
111 pam_init();
112 for ( int i = 1 ,_=strlen(S+1); i <= _ ; i++) extend(S[i]-'a',i);
113 LL ans = solve();
114 cout<<ans<<endl;
115
116
117 #ifndef ONLINE_JUDGE
118 fclose(stdin);
119 #endif
120 return 0;
121}