【题解】P4503 [CTSC2014]企鹅QQ(哈希)

考虑这样一种做法，将每个字符串的删去某个字符的新字符串的哈希值存下来，然后最后\(sort\)一遍双指针统计每个值相同的数的个数\(x\)，这个\(x\)对答案的贡献是\({x \choose 2}\)

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxs=2e2+5;

int n,len,S,cnt;

char c[maxs];

int ha1[maxs],ha2[maxs];

int s1[maxs],s2[maxs];

int base1[maxs],base2[maxs];

const int mod1=998244353,mod2=993244853;

const int seed1=233,seed2=666;

pair<int,int> data[200*30001];

inline void insert(const char*c){

      for(int t=1;t<=len;++t) ha1[t]=(1ll*ha1[t-1]*seed1+c[t])%mod1,ha2[t]=(1ll*ha2[t-1]*seed2+c[t])%mod2;

      for(int t=len;t;--t) s1[t]=(1ll*s1[t+1]*seed1+c[t])%mod1,s2[t]=(1ll*s2[t+1]*seed2+c[t])%mod2;

      for(int t=1;t<=len;++t) data[++cnt]={(0ll+ha1[t-1]+1ll*base1[t]*s1[t+1]%mod1)%mod1,(0ll+ha2[t-1]+1ll*base2[t]*s2[t+1]%mod2)%mod2};

}

int main(){

      base1[0]=base2[0]=1;

      n=qr(); len=qr(); S=qr();

      for(int t=1;t<=len;++t) base1[t]=1ll*base1[t-1]*seed1%mod1,base2[t]=1ll*base2[t-1]*seed2%mod2;

      for(int t=1;t<=n;++t) scanf("%s",c+1),insert(c);//cout<<(c+1)<<endl;

      sort(data+1,data+cnt+1);

      ll ans=0;

      for(int t=1,r=1;t<=cnt;t=++r){

	    while(data[t]==data[r+1]) ++r;

	    if(r>t) ans=ans+((r-t+1LL)*(r-t)>>1);

      }

      printf("%lld\n",ans);

      return 0;

}

巴特西

【题解】P4503 [CTSC2014]企鹅QQ(哈希)

【题解】P4503 [CTSC2014]企鹅QQ(哈希)

最新文章

热门文章