1 条题解

  • 0
    @ 2024-1-18 9:10:56

    求助:为什么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;
    }
    
    • 1

    信息

    ID
    2022
    时间
    2000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    70
    已通过
    4
    上传者