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

首先做这道题要掌握一个算法——[Manacher算法](https://www.cnblogs.com/lykkk/p/10460087.html) 简要说他就是用来解决回文串相关问题的算法，并不高深 由题意可知，显然**每一个和谐群体就是一个长度为奇数的回文串** 用Manacher可以求每个位置的回文半径 因为我们只要求奇数个的回文串，那么显然我们不需要在字符串里添加一些无关字符 那么我们用Manacher求出以当前位置为中心的最长回文子串长度 所以我们就会在求的同时搞出最长的len 然后根据对称性可知也有长为**len*2-1**的回文子串，接着我们只需要统计一下就可以了 注意我们**只要奇数个，去掉偶数个** 因为数据范围过大，所以我们要**Fast_Pow**使得不会爆掉 那么。。。下面我们来看一下我~~优秀的代码~~ ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long const int mod = 19930726; const int N = 1100000; char s[N],str[N*2]; int p[N*2],cnt[N]; int len,n; ll ans=1,k; ll ksm(int x,int y) {//因为数据范围很大容易爆掉，所以就要Fast_Pow if(x==1) return 1; ll res=1,base=x; while(y) { if(y&1) res=(res*base)%mod; base=(base*base)%mod; y>>=1; } return res; } void manacher() {//Manacher模板，详见洛谷P3805 for(int i=1; i<=len; i++) str[i*2-1]='%',str[i*2]=s[i]; str[len=len*2+1]='%'; int id=0,mx=0; for(int i=1; i<=len; i++) { if(i<mx) p[i]=min(p[id*2-i],mx-i); else p[i]=1; while(p[i]+i<=len && i-p[i]>=1 && str[i+p[i]]==str[i-p[i]]) p[i]++; if(p[i]+i>mx) id=i,mx=i+p[i]; if((p[i]-1)%2) cnt[p[i]-1]++; } } int main() { int sum=0; cin>>n>>k>>s+1; len=n; manacher(); for(int i=n; i>=1; --i) {//根据题意常规操作 if(i%2==0) continue; sum+=cnt[i]; if(k>=sum) { ans=(ans*ksm(i,sum))%mod; k-=sum; } else { ans=(ans*ksm(i,k))%mod; k-=sum; break; } } if(k>0) ans=-1; cout<<ans; return 0; } ```