「BZOJ3555」[CTSC2014]企鹅QQ

Description

PenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。
小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名称总是很相似的,例如Penguin1Penguin2Penguin3\cdots\cdots于是小Q决定先对这种相似的情形进行统计。
小Q定义,若两个账户名称是相似的,当且仅当这两个字符串等长且恰好只有一位不同。例如Penguin1Penguin2是相似的,但Penguin12Penguin不是相似的。而小Q想知道,在给定的 个账户名称中,有多少对是相似的。
为了简化你的工作,小Q给你的nn个字符串长度均等于mm,且只包含大小写字母、数字、下划线以及@共64种字符,而且不存在两个相同的账户名称。

Input

第一行包含三个正整数nnmmss。其中nn表示账户名称数量,mm表示账户名称长度,ss用来表示字符集规模大小,它的值只可能为226464
ss等于22,账户名称中只包含字符0122种字符;
ss等于6464,账户名称中可能包含大小写字母、数字、下划线以及‘@’共64种字符。
随后nn行,每行一个长度为mm的字符串,用来描述一个账户名称。数据保证nn个字符串是两两不同的。

Output

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

Sample Input

1
2
3
4
5
4 3 64
Fax
fax
max
mac

Sample Output

1
4

HINT

N30000,L200,S64N\leq30000,L\leq 200,S\leq64

Solution

一眼hash,mapTLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 31000;
const int L = 210;
int n, m;
struct H {
ll p;
ll v[L], bin[L];
ll Q(int x, int y) {
if(x > y) return 0;
return (v[y] - v[x-1] * bin[y - x + 1]%p + p) % p;
}
int query(int x) {
return (Q(x + 1, m) * bin[x - 1] % p + Q(1, x - 1)) % p;
}
}h1,h2;
pii a[N][L];
char s[L];
ll ksm(ll x, ll y, ll p) {
ll res = 1;
for(; y; y >>= 1, x = x * x % p)
if(y & 1) res = res * x % p;
return res;
}
map<pii,int>c;
int main() {
n = read(), m = read(); read();
h1.p = 1e9 + 7;
h2.p = 1e9 + 9;
h1.bin[0] = h2.bin[0] = 1;
for(int i = 1; i <= 200; ++i) {
h1.bin[i] = h1.bin[i-1] * 255 % h1.p;
h2.bin[i] = h2.bin[i-1] * 255 % h2.p;
}
ll ans = 0;
for(int i = 1; i <= n; ++i) {
scanf("%s",s+1);
for(int j = 1; j <= m; ++j) {
h1.v[j] = (h1.v[j - 1] * 255 + s[j]) % h1.p;
h2.v[j] = (h2.v[j - 1] * 255 + s[j]) % h2.p;
}
for(int j = 1; j <= m; ++j) {
int t1 = h1.query(j);
int t2 = h2.query(j);
a[i][j] = mk(t1, t2);
//ans += v[j][mk(t1,t2)];
}
}
for(int i = 1; i <= m; ++i) {
c.clear();
for(int j = 1; j <= n; ++j) {
ans += c[mk(a[j][i].fi,a[j][i].nd)];
++c[mk(a[j][i].fi,a[j][i].nd)];
}
}
writeln(ans);
return 0;
}

std

我们一位一位来。
对于得到的hashhash,直接v1p2+v2v_1p_2+v_2,然后排序一下。
遇到相同的,ans+=nowans +=now,now=now+1now=now+1否则now=1now=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 31000;
const int L = 210;
int n, m;
struct H {
ll p;
ll v[L], bin[L];
ll Q(int x, int y) {
if(x > y) return 0;
return (v[y] - v[x-1] * bin[y - x + 1]%p + p) % p;
}
int query(int x) {
return (Q(x + 1, m) * bin[x - 1] % p + Q(1, x - 1)) % p;
}
}h1,h2;
pii a[N][L];
char s[L];
ll tmp[N];
int main() {
freopen("3555.in","r",stdin);
freopen("3555.out","w",stdout);
n = read(), m = read(); read();
h1.p = 1e9 + 7;
h2.p = 1e9 + 9;
h1.bin[0] = h2.bin[0] = 1;
for(int i = 1; i <= 200; ++i) {
h1.bin[i] = h1.bin[i-1] * 255 % h1.p;
h2.bin[i] = h2.bin[i-1] * 255 % h2.p;
}
ll ans = 0;
for(int i = 1; i <= n; ++i) {
scanf("%s",s+1);
for(int j = 1; j <= m; ++j) {
h1.v[j] = (h1.v[j - 1] * 255 + s[j]) % h1.p;
h2.v[j] = (h2.v[j - 1] * 255 + s[j]) % h2.p;
}
for(int j = 1; j <= m; ++j) {
int t1 = h1.query(j);
int t2 = h2.query(j);
a[i][j] = mk(t1, t2);
}
}
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) tmp[j] = a[j][i].fi * h2.p + a[j][i].nd;
int now = 0;
sort(tmp + 1, tmp + 1 + n);
for(int j = 1; j <= n; ++j) if(tmp[j] == tmp[j - 1]) ans += now,++now;
else now = 1;
}
writeln(ans);
return 0;
}