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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <bits/stdc++.h>
using namespace std;
const int N = 262144;
inline char nc() {
static char buf[100000], *p1 = buf, *p2 = buf;
if (p1 == p2) {
p2 = (p1 = buf) + fread(buf, 1, 100000, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline void read(int &x) {
char c = nc(), b = 1;
for (; !(c >= '0' && c <= '9'); c = nc())
if (c == '-') b = -1;
for (x = 0; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = nc())
;
x *= b;
}
int pos[N];
struct comp {
double r, i;
comp(double _r = 0, double _i = 0) : r(_r), i(_i) {}
comp operator+(const comp &x) { return comp(r + x.r, i + x.i); }
comp operator-(const comp &x) { return comp(r - x.r, i - x.i); }
comp operator*(const comp &x) {
return comp(r * x.r - i * x.i, i * x.r + r * x.i);
}
comp conj() { return comp(r, -i); }
} A[N], B[N];
const double pi = acos(-1.0);
void FFT(comp a[], int n, int t) {
for (int i = 1; i < n; i++)
if (pos[i] > i) swap(a[i], a[pos[i]]);
for (int d = 0; (1 << d) < n; d++) {
int m = 1 << d, m2 = m << 1;
double o = pi * 2 / m2 * t;
comp _w(cos(o), sin(o));
for (int i = 0; i < n; i += m2) {
comp w(1, 0);
for (int j = 0; j < m; j++) {
comp &A = a[i + j + m], &B = a[i + j], t = w * A;
A = B - t;
B = B + t;
w = w * _w;
}
}
}
if (t == -1)
for (int i = 0; i < n; i++) a[i].r /= n;
}
void mul(long long *a, long long *b, long long *c, int k) {
int i, j;
for (i = 0; i < k; i++) A[i] = comp(a[i], b[i]);
j = __builtin_ctz(k) - 1;
for (int i = 0; i < k; i++) {
pos[i] = pos[i >> 1] >> 1 | ((i & 1) << j);
}
FFT(A, k, 1);
for (int i = 0; i < k; i++) {
j = (k - i) & (k - 1);
B[i] = (A[i] * A[i] - (A[j] * A[j]).conj()) * comp(0, -0.25);
}
FFT(B, k, -1);
for (int i = 0; i < k; i++) c[i] = (long long)(B[i].r + 0.5);
}
int T, n, len, a[N], b[N], c[N];
long long fa[N], fb[N], fc[N], ans;
void doit(int *a, int *b, int *c, int N) {
for (int i = 0; i < N; i++) fa[i] = fb[i] = 0;
for (int i = 1; i <= n; i++) fa[a[i]]++;
for (int i = 1; i <= n; i++) fb[b[i]]++;
mul(fa, fb, fc, N);
for (int i = 1; i <= len; i++) fc[i] = fc[i] + fc[i - 1];
for (int i = 1; i <= n; i++) ans = ans - fc[c[i] - 1];
}
void doitsp(int *a, int *b, int *c) {
for (int i = 1; i <= len; i++) fc[i] = 0;
for (int i = 1; i <= n; i++) fc[c[i]]++;
for (int i = len - 1; i; i--) fc[i] = fc[i] + fc[i + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if(a[i] + b[j] + 1 <= len) ans -= fc[a[i] + b[j] + 1];
}
}
int main() {
read(T);
for (int cas = 1; cas <= T; cas++) {
read(n);
len = 0;
ans = 1ll * n * n * n;
for (int i = 1; i <= n; i++) read(a[i]), len = max(a[i], len);
for (int i = 1; i <= n; i++) read(b[i]), len = max(b[i], len);
for (int i = 1; i <= n; i++) read(c[i]), len = max(c[i], len);
if (n <= 1000) {
doitsp(a, b, c);
doitsp(b, c, a);
doitsp(c, a, b);
printf("Case #%d: %lld\n", cas, ans);
continue;
}
int N = 1;
while (N < len) N <<= 1;
N <<= 1;
doit(a, b, c, N);
doit(b, c, a, N);
doit(c, a, b, N);
printf("Case #%d: %lld\n", cas, ans);
}
return 0;
}
|
