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
| #include<cstdio>
#include<algorithm>
#define RG register
const int maxn(2e6 + 10);
unsigned int SA, SB, SC;
int n, a[maxn], b[maxn], c[maxn], C1[maxn], C2[maxn], C3[maxn];
long long ans;
struct qry { int a, b, c; } q[maxn];
inline void swap(int &x, int &y) { static int t; t = x; x = y; y = t; }
inline unsigned int Random()
{
SA ^= SA << 16; SA ^= SA >> 5; SA ^= SA << 1;
static unsigned int t; t = SA; SA = SB; SB = SC; SC ^= t ^ SA;
return SC;
}
inline void add(int *C, int x) { while(x <= n) ++C[x], x += x & -x; }
inline int query(int *C, int x) { int ans = 0; while(x) ans += C[x], x -= x & -x; return ans; }
int main()
{
RG int i;
scanf("%d%u%u%u", &n, &SA, &SB, &SC);
for(i = 1; i <= n; ++i) a[i] = i;
for(i = 1; i <= n; ++i) b[i] = i;
for(i = 1; i <= n; ++i) c[i] = i;
for(i = 1; i <= n; ++i) swap(a[i], a[1 + Random() % n]);
for(i = 1; i <= n; ++i) swap(b[i], b[1 + Random() % n]);
for(i = 1; i <= n; ++i) swap(c[i], c[1 + Random() % n]);
for(i = 1; i <= n; ++i) q[a[i]] = (qry) {a[i], b[i], c[i]};
for(i = 1; i <= n; ++i) ans += query(C1, q[i].b), add(C1, q[i].b);
for(i = 1; i <= n; ++i) q[b[i]] = (qry) {a[i], b[i], c[i]};
for(i = 1; i <= n; ++i) ans += query(C2, q[i].c), add(C2, q[i].c);
for(i = 1; i <= n; ++i) q[c[i]] = (qry) {a[i], b[i], c[i]};
for(i = 1; i <= n; ++i) ans += query(C3, q[i].a), add(C3, q[i].a);
printf("%lld\n", (ans - 1ll * n * (n - 1) / 2) >> 1);
return 0;
}
|