为何n*l*log(n*l)的做法过不了?
查看原帖
为何n*l*log(n*l)的做法过不了?
782904
哈哈人生楼主2024/7/15 17:01

难道是常数太大?WA能理解,TLE实在是不能。

#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
int pw1[205],pw2[205];
int rd(int l,int r){
	return rand()%(r-l+1)+l;
}
void init(){
	for(int i=0;i<=200;i++)pw1[i]=rd(1,M);
	for(int i=0;i<=200;i++)pw2[i]=rd(1,M);
}
int ohash1(string s){
	int ret=0;
	for(int i=0;i<s.size();i++){
		ret=(ret+s[i]%M*pw1[i]%M)%M;
	}
	return ret;
}
int ohash2(string s){
	int ret=0;
	for(int i=0;i<s.size();i++){
		ret=(ret+s[i]%M*pw2[i]%M)%M;
	}
	return ret;
}
int n,l,g,h1[30005],h2[30005],zh[6000006],tot=0,zh2[6000006],tot2=0;
string s[30005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	srand(time(0));
	init();
	cin>>n>>l>>g;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		h1[i]=ohash1(s[i]),h2[i]=ohash2(s[i]);
		for(int j=0;j<l;j++){
			zh[++tot]=(h1[i]-pw1[j]%M*s[i][j]%M+M)%M;
			zh2[++tot2]=(h2[i]-pw2[j]%M*s[i][j]%M+M)%M;
		}
	}
	sort(zh+1,zh+tot+1);
	sort(zh2+1,zh2+tot2+1);
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<l;j++){
			int l=lower_bound(zh+1,zh+tot+1,(h1[i]-pw1[j]%M*s[i][j]%M+M)%M)-zh-1,r=upper_bound(zh+1,zh+tot+1,(h1[i]-pw1[j]%M*s[i][j]%M+M)%M)-zh-1;
			int l2=lower_bound(zh2+1,zh2+tot2+1,(h2[i]-pw2[j]%M*s[i][j]%M+M)%M)-zh2-1,r2=upper_bound(zh2+1,zh2+tot2+1,(h2[i]-pw2[j]%M*s[i][j]%M+M)%M)-zh2-1;
			ans+=min(r-l,r2-l2)-1;
		}
	}
	cout<<ans/2;
	return 0;
}
2024/7/15 17:01
加载中...