题面
Solution
首先做这道题要掌握一个算法——Manacher算法
简要说他就是用来解决回文串相关问题的算法，并不高深
由题意可知，显然每一个和谐群体就是一个长度为奇数的回文串
用Manacher可以求每个位置的回文半径
因为我们只要求奇数个的回文串，那么显然我们不需要在字符串里添加一些无关字符
那么我们用Manacher求出以当前位置为中心的最长回文子串长度
所以我们就会在求的同时搞出最长的len
然后根据对称性可知也有长为len*2-1的回文子串，接着我们只需要统计一下就可以了
注意我们只要奇数个，去掉偶数个
因为数据范围过大，所以我们要Fast_Pow使得不会爆掉
AC代码
#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;
}
完结，撒花！！
