UVa 13154 - Extreme XOR Sum

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 觀察
    2. 4.2. 如何在 Sierpinski sieve 找到非零係數的位置

Problem

給一長度為 $N$ 的整數序列,詢問任意區間的極端異或和 Extreme XOR Sum。

定義 Extreme XOR Sum 為一系列操作的最後一個值

  • 當長度 $n>1$ 時,將陣列縮小為 $n-1$
  • $[a_0, a_1, a_2, \cdots, a_{n-1}]$,每一個元素與後一個元素運行互斥或,將會被轉換成 $[a_0 \oplus a_1, a_1\oplus a_2, a_2 \oplus a_3, \cdots, a_{n-2}\oplus a_{n-1}]$
  • 直到只剩下一個元素,即為 Extreme XOR Sum

Sample Input

1
2
3
4
5
6
7
1
5
1 4 6 7 8
3
0 0
0 1
2 4

Sample Output

1
2
3
4
Case 1:
1
5
14

Solution

這題詢問次數非常多,一般運行將對每一個詢問達到 $O(N)$ 的複雜度,這很容易得到 TLE。從大多的數據結構,如線段樹、塊狀表 … 等,他們提供高效率的查找效能,但也必須符合某些條件才能使用。因此,在此題若要符合結合律將變得相當困難。

觀察

假設要計算陣列 $[1, 4, 6, 7, 8]$ 的值時

  • 第一步,$[1 \oplus 4, 4 \oplus 6, 6 \oplus 7, 7 \oplus 8]$
  • 第二步,$[1 \oplus 4 \oplus 4 \oplus 6, \cdots]$
  • 如此類推下去,XOR 有結合律,我們發現到各別使用了 1 次 $a_0$、4 次 $a_1$、6 次 $a_2$、4 次 $a_3$ 和 1 次 $a_4$

對於不同的長度,我們發現到是二項係數的配對情況。由於偶數次的 XOR 會互消,只需要計算出現奇數次的即可,因此我們列出二項次數模二的情況,進而得到 Sierpinski triangle/Sierpinski sieve。即使知道 Sierpinski sieve 是二項係數模二的結果,我們仍不知道要怎麼套用結合律達到剖分加速的條件。

二項係數的公式如下

$$\begin{align*} \binom{n}{m} &= \binom{n-1}{m-1} + \binom{n-1}{m} \\ &= \frac{n!}{m!(n-m)!} \end{align*}$$

階層運算在數學運算上的性質並不多,逼得我們只好往碎形上觀察,以下列出前幾項的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

發現它是一個很有趣的碎形,每個三角形大小都是以二的冪次的。我們按照 $2^3 = 8$ 切割一下上圖,並且把右邊斜的補上 0 得到下圖。

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
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
^---------------
1 0 0 0 0 0 0 0 |1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 |1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 |1 0 1 0 0 0 0 0
1 1 1 1 0 0 0 0 |1 1 1 1 0 0 0 0
1 0 0 0 1 0 0 0 |1 0 0 0 1 0 0 0
1 1 0 0 1 1 0 0 |1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0 |1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 |1 1 1 1 1 1 1 1
^----------------^--------------
1 0 0 0 0 0 0 0 |0 0 0 0 0 0 0 0 |1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 |0 0 0 0 0 0 0 0 |1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 |0 0 0 0 0 0 0 0 |1 0 1 0 0 0 0 0
1 1 1 1 0 0 0 0 |0 0 0 0 0 0 0 0 |1 1 1 1 0 0 0 0
1 0 0 0 1 0 0 0 |0 0 0 0 0 0 0 0 |1 0 0 0 1 0 0 0
1 1 0 0 1 1 0 0 |0 0 0 0 0 0 0 0 |1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0 |0 0 0 0 0 0 0 0 |1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 |0 0 0 0 0 0 0 0 |1 1 1 1 1 1 1 1
^ ^ ^
箭頭表示本身也是 Sierpinski sieve
區塊縮影得到 miniature pattern 也是 Sierpinski sieve
1
1 1
1 0 1

得到數個一模一樣的子圖,上述全零和非零的區塊,又恰好構成 Sierpinski sieve。這告訴我們任何操作全都要以二的冪次為基準,且合併區段時須以二項係數為係數。設定 pattern 大小為 $M=2^{\lceil \log_2 N\rceil}$,最後得到 miniature pattern。在同一層中,非零構成的條紋都是相同的模式,例如上述得圖中,最後一層的箭號組合必然是 101 或者是 000,最後得到下列公式計算條紋。

$A_{i, j} = A_{i-1}{j} \oplus A_{i-1,j+M}$

接下來,我們將需要確定每一個條紋 (stripe) 是否使用全零或者非零,只需要查找 miniature pattern 相應的係數即可。

如何在 Sierpinski sieve 找到非零係數的位置

$\binom{n}{i} \mod 2 = 1$,必滿足 $n\&i = i$。其證明從數學歸納法來,由二冪次的長度碎形著手,移除最高位的 1 得到 $i'$,從 $i'$ 舊有位置集合,保留此集合,並對每一個元素增加二的冪次得到碎形的另一邊。

故可利用下述算法,準確地找到每一個非零的係數位置

1
2
for (int pos = n; pos; pos = (pos-1)&n)
C[n][pos] mod 2 = 1

最後附上優化後得到 Rank 1 的程序 0.040 s

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
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
static const int M = (1<<7);
static const int MAXN = 10005;
static int A[M+1][MAXN];
void miniature(int n) {
for (int i = 1; i*M < n; i++) {
for (int j = 0; j+i*M < n; j++)
A[i][j] = A[i-1][j] ^ A[i-1][j+M];
}
}
int extract(int l, int r) {
const int n = r-l;
const int m = n/M;
const int o = n%M;
int ret = A[m][l];
for (int i = o; i; i = (i-1)&o)
ret ^= A[m][l+i];
return ret;
}
namespace MM {
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
class Print {
public:
static const int N = 1048576;
char buf[N], *p, *end;
Print() {
p = buf, end = buf + N - 1;
}
void printInt(int x, char padding) {
static char stk[16];
int idx = 0;
stk[idx++] = padding;
if (!x)
stk[idx++] = '0';
while (x)
stk[idx++] = x%10 + '0', x /= 10;
while (idx) {
if (p == end) {
*p = '\0';
printf("%s", buf), p = buf;
}
*p = stk[--idx], p++;
}
}
void flush() {
*p = '\0', p = buf;
printf("%s", buf);
}
static inline void online_printInt(int x) {
static char ch[16];
static int idx;
idx = 0;
if (x == 0) ch[++idx] = 0;
while (x > 0) ch[++idx] = x % 10, x /= 10;
while (idx)
putchar(ch[idx--]+48);
}
~Print() {
*p = '\0';
printf("%s", buf);
}
} bprint;
}
int main() {
int testcase, cases = 0;
int n, m;
// scanf("%d", &testcase);
MM::ReadInt(&testcase);
while (testcase--) {
// scanf("%d", &n);
MM::ReadInt(&n);
for (int i = 0; i < n; i++)
// scanf("%d", &A[0][i]);
MM::ReadInt(&A[0][i]);
miniature(n);
// scanf("%d", &m);
MM::ReadInt(&m);
printf("Case %d:\n", ++cases);
for (int i = 0; i < m; i++) {
int l, r;
// scanf("%d %d", &l, &r);
MM::ReadInt(&l), MM::ReadInt(&r);
// printf("%d\n", extract(l, r));
MM::bprint.printInt(extract(l, r), '\n');
}
MM::bprint.flush();
}
return 0;
}
/*
1
5
1 4 6 7 8
3
0 0
0 1
2 4
*/