1 solutions
-
1
看错题的痛,我的一下午没了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; }
- 1
Information
- ID
- 6523
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- (None)
- # Submissions
- 31
- Accepted
- 5
- Uploaded By