难道是常数太大?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;
}