3555: [Ctsc2014]企鹅QQ

Time Limit: 20 Sec  Memory Limit: 256 MB

Submit: 696  Solved: 294

[][][]

Description

PenguinQQ是中国最大、最具影响力的SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。

小Q是PenguinQQ网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小Q发现同一个人注册的账户名称总是很相似的，例如Penguin1，Penguin2，Penguin3……于是小Q决定先对这种相似的情形进行统计。

小Q定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。而小Q想知道，在给定的 个账户名称中，有多少对是相似的。

为了简化你的工作，小Q给你的 个字符串长度均等于 ，且只包含大小写字母、数字、下划线以及共64种字符，而且不存在两个相同的账户名称。

Input

第一行包含三个正整数 ， ， 。其中 表示账户名称数量， 表示账户名称长度， 用来表示字符集规模大小，它的值只可能为2或64。

若 等于2，账户名称中只包含字符‘0’和‘1’共2种字符；

若 等于64，账户名称中可能包含大小写字母、数字、下划线以及共64种字符。

随后 行，每行一个长度为 的字符串，用来描述一个账户名称。数据保证 个字符串是两两不同的。

Output

仅一行一个正整数，表示共有多少对相似的账户名称。

Sample Input

4 3 64

Fax

fax

max

mac

Sample Output

4

HINT

 

4对相似的字符串分别为：Fax与fax，Fax与max，fax与max，max与mac。N<=30000,L<=200,S<=64

 

Source

 

题解：显然的字符串哈希。。。

这里由于是恰好一位不一样，所以可以在进行双值哈希的时候统一抹掉那一位，然后如果仅仅是那一位不一样的话，那么剩下的部分必定哈希值一样，所以接下来排个序求出各种哈希值出现的次数，然后统计下即可（话说随机化快排居然比二分快排慢那么多是什么梗QAQ，最下面的那个是二分快排，上面是两个随机快排）

（还有我貌似成了第一个在BZOJ上面用pascal秒掉此题的人好开心^_^）

1 /**************************************************************  2     Problem: 3555  3     User: HansBug  4     Language: Pascal  5     Result: Accepted  6     Time:18504 ms  7     Memory:10764 kb  8 ****************************************************************/  9   10 const p=314159;q=951413; 11 type arr=array[0..50000,1..2] of int64; 12 var 13    i,j,k,l,m,n,t:longint; 14    ans,x,y:int64;ch:char; 15    ap:array[char] of longint; 16    ml,a,b:arr; 17    ss:ansistring; 18    st:array[0..50000] of ansistring; 19 procedure sort(l,r:longint;var a:arr); 20           var i,j:longint;x,y,z:int64; 21           begin 22                i:=l;j:=r;x:=a[(l+r) div 2,1];y:=a[(l+r) div 2,2]; 23                repeat 24                      while (a[i,1]
      
       x) or ((a[j,1]=x) and (a[j,2]>y)) do dec(j); 26                      if i<=j then 27                         begin 28                              z:=a[i,1];a[i,1]:=a[j,1];a[j,1]:=z; 29                              z:=a[i,2];a[i,2]:=a[j,2];a[j,2]:=z; 30                              inc(i);dec(j); 31                         end; 32                until i>j; 33                if i
       
        b[k,1]) or (b[j,2]<>b[k,2]) then 98                           begin 99                                ans:=ans+(l*(l-1)) div 2;100                                k:=j;l:=1;101                           end102                        else inc(l);103                   end;104          end;105      writeln(ans);106      readln;107 end.