1 solutions
Information
- ID
- 6523
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- (None)
- # Submissions
- 42
- Accepted
- 6
- Uploaded By
看错题的痛,我的一下午没了QAQ,写个题解报复一下 将前面的马拉车拿来改造即可,注意因为数据很多,会超时,所以要用到快速幂,还要用到一下前缀和,尤其注意题目说奇数(划重点T_T)个字符的回文子串。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define mod 19930726
typedef long long ll;
const int N=1e7+5;
char s[N],tmp[2*N];
int len[2*N],flag;
ll length[2*N],sum[2*N],ed=1,k,n,m;
bool v[2*N];
ll fast(ll x,ll k)//快速幂
{
ll ans=1;
while(k){
if(k&1)ans=ans*x%mod;
k>>=1;
x=x*x%mod;
}
return ans%mod;
}
ll init(char *str){//初始化构造字符串
int cou=0,len=n;
tmp[cou++]='$';
for(int i=0;i<len;i++){
tmp[cou++]='#';
tmp[cou++]=str[i];
}
tmp[cou++]='#';
return 2*len+1;
}
ll Manacher(char *str){
ll nn=init(str);
int mx=0,p=0,ans=0;
for(int i=1;i<=nn;i++){
if(i<mx){
len[i]=min(mx-i,len[2*p-i]);
}
else {
len[i]=1;
}
while(tmp[i-len[i]]==tmp[len[i]+i]){
len[i]++;
}
if(i+len[i]>mx){
mx=i+len[i];
p=i;
}
ans=len[i]-1;
if(length[ans]==0&&ans%2!=0){//记录第一次遇到的长度,去掉偶数长串
sum[k]=ans;
length[ans]++;//记录次数
k++;
}
else length[ans]++;//记录次数
}
sort(sum,sum+k);//排一次序
int g=sum[k-1]-1;//求最大用于求前缀和
for(int i=g;i>0;i--){//前缀和
if(length[i]==0&&length[i+2]){//创建新长度,防止多开,防止多开应该可以不要
sum[k]=i;
k++;
}
length[i]+=length[i+2];
}
sort(sum,sum+k);//再更新一次排序
for(int j=0;m;j++){
ll a=sum[k-1-j];
ll b=length[sum[k-1-j]];
if(a==0){//sum数组用到了0证明k过大,需要特判
cout<<"-1";
flag=1;
break;
}
if(b<=m){
ed=(ed*fast(a,b))%mod;
m-=b;
}
else {
ed=(ed*fast(a,m))%mod;
break;
}
ed=ed%mod;
}
ed%=mod;
return ed;
}
int main(){
cin>>n>>m;
scanf("%s",s);
ll p=Manacher(s);
if(!flag)cout<<p;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.