2017-04-28

UVa 13154 - Extreme XOR Sum

1. Problem
2. Sample Input
3. Sample Output
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
5
1  4  6  7  8
3
0  0
0  1
2  4

Sample Output

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
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
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

#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
*/

Morris' Blog