题解 P1659 【[国家集训队]拉拉队排练】

顾z

2018-08-04 09:32:04

Solution

**题目描述** n个女生举牌子(只含有26个小写字母,长度为n的字符串), 如果连续的一段女生,有奇数个,并且她们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。 现在想找出所有和谐小群体,并且按照女生的个数降序排序之后,前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大,输出除以19930726的余数。 **分析** 显然,一个和谐小群体是一个长度为奇数的回文串。 ~~理所当然地~~我们想到了manacher算法 **manacher**算法可以求出每个位置的回文半径. 所以我们可以用manacher来解决此题 然后因为这个题只需要求出奇数长度的回文串 所以不需要考虑插入字符(其实也可以插入 由于最后一个点十分大 k<10^12(辣么长 所以需要**快速幂**加速一下 **掉坑现场** 重点 ~~个人认为~~ 求出了某一位置的回文半径 就像样例解释中一样 eg:a b a b a 回文半径为5 但它也包含了 a bab ababa! 即如果一个值为x(x>1)那x-1,x-2.....也存在 所以我们需要**前缀和**来做 (感觉不应该叫前缀和啊emm 但又感觉差不多) 我们可以用**桶**存储一下回文半径,倒着搜一遍即可 _(:з」∠)_ ~~(胳膊没了~~ ----------------代码------------------ #### ——代码部分参考[bolg @five20](https://www.cnblogs.com/five20/p/8616294.html) ```cpp #include<bits/stdc++.h> #define IL inline #define RI register long long #define N 1000008 #define mod 19930726 char s[N<<1],ch[N]; long long n,k,len,RL[N<<1],mxxnum,sum,ans=1; long long MaxRight,center,tong[N<<1]; IL long long ksm(long long x,long long y) { long long res=1; for(;y;y>>=1,x=x*x%mod) if(y&1)res=res*x%mod; return res; } int main() { scanf("%lld%lld",&n,&k); scanf("%s",s+1); for(RI i=1;i<=n;i++) { if(i<=MaxRight)RL[i]=std::min(MaxRight-i,RL[2*center-i]); else RL[i]=1; while(i+RL[i]<=n&&i-RL[i]>=0&&s[i+RL[i]]==s[i-RL[i]])++RL[i]; if(i+RL[i]-1>MaxRight)MaxRight=i+RL[i]-1,center=i; tong[2*RL[i]-1]++; } //for(RI i=1;i<=n;i++)printf("%lld ",tong[i]); if(n%2!=1)n--; for(RI i=n;i>=1;i-=2) { sum+=tong[i]; if(sum>k) { ans=ans*ksm(i,k)%mod; break; } else { ans=ans*ksm(i,sum)%mod; k-=sum; } } if(sum<k)printf("-1"); else printf("%lld\n",ans); } ``` ~~好了好了 我知道丑了emmmm~~