1 条题解
-
0
求助:为什么0分?
#include<bits/stdc++.h> #define int long long using namespace std; long long slen,val[1000010],vall[1000010],p[1000010],l,r; const long long mod=998244353; long long gethash(long long l,long long r){ return (val[r]-val[l-1]*p[r-l+1]%mod+mod)%mod; } long long gethash_last(long long l,long long r){ return (vall[r]-vall[l-1]*p[r-l+1]%mod+mod)%mod; } long long check(long long len,long long x){ long long L=1,R=len; // cout<<"len="<<len<<"\n"; while(L<=R){ long long mid=(L+R)>>1; if(gethash(x-mid,x-1)==gethash_last(slen-(x+mid)+1,slen-(x+1)+1)) L=mid+1; else R=mid-1; } return (L+1)/2; } long long check2(long long len,long long x){ long long L=1,R=len; // cout<<"len="<<len<<"\n"; while(L<=R){ long long mid=(L+R)>>1; if(gethash(x-mid+1,x)==gethash_last(slen-(x+mid)+1,slen-(x+1)+1)) L=mid+1; else R=mid-1; } return R; } string s,t; long long ans=0; signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>s,slen=s.length(),r=slen,l=1,p[0]=1; for(int i=slen-1;i>=0;i--) t+=s[i]; for(int i=1;i<=1000000;i++) p[i]=(p[i-1]*997LL)%mod; for(int i=1;i<=slen;i++) val[i]=(val[i-1]*997LL+s[i-1])%mod; for(int i=1;i<=slen;i++) vall[i]=(vall[i-1]*997LL+t[i-1])%mod; for(int i=1;i<=slen;i++){ ans+=check(min(i,slen-i+1),i); // cout<<check(min(i,slen-i+1),i)<<" "; } // cout<<"\n"; for(int i=1;i<=slen/2;i++){ ans+=check2(i,i); // cout<<check2(i,i)<<" "; } // cout<<"\n"<<ans<<"\n"; cout<<ans<<"\n"; return 0; }
信息
- ID
- 2022
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 70
- 已通过
- 4
- 上传者