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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int maxS = 80;
int N, MOD[maxn];
char s[maxn];
struct get_MOD {
int value[maxS + 5];
bool operator < (const get_MOD&b) const {
for (int i = 1; i <= maxS; ++i)
if (value[i] != b.value[i]) return value[i] < b.value[i];
return false;
}
}a[maxn];
map<get_MOD , int> pc;
const int E9 = 1e9;
void init() {
for (int i = 1; i <= maxS; ++i) {
MOD[i] = E9 + ((long long)rand() * rand() % E9);
}
}
void input(get_MOD &a, int x) {
for (int i = 1; i <= maxS; ++i) {
a.value[i] = (((long long)a.value[i] * 10) + x) % MOD[i];
}
}
get_MOD mul(get_MOD &a, get_MOD &b) {
get_MOD X;
for (int i = 1; i <= maxS; ++i) {
X.value[i] = (long long)a.value[i] * b.value[i] % MOD[i];
}
return X;
}
int main() {
srand(rand());
init();
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%s", s);
int g = strlen(s);
for (int j = 0; j < g; ++j) {
input(a[i], s[j] - '0');
}
pc[a[i]]++;
}
int ans = 0;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
get_MOD temp = mul(a[i], a[j]);
if (pc.count(temp)) ans += pc[temp];
}
}
printf("%d", ans);
return 0;
}
|
