GD vs ZJ Problem E

Brute.java

import java.io.*;
import java.math.*;
import java.util.*;

public class Brute {
    public void run() {
        try {
            int testCount = reader.nextInt();
            for (int t = 1; t <= testCount; ++ t) {
                int n = reader.nextInt();
                int[] a = new int[n];
                for (int i = 0; i < n; ++ i) {
                    a[i] = reader.nextInt();
                }
                int result = 0;
                for (int i = 0; i < n; ++ i) {
                    int sum = 0;
                    for (int j = i; j < n; ++ j) {
                        sum += a[j];
                        result ^= sum;
                    }
                }
                writer.println(String.format("Case #%d: %d", t, result));
            }
        } catch (IOException ex) {
            assert false;
        }
        writer.close();
    }

    Brute() {
        reader = new InputReader(System.in);
        writer = new PrintWriter(System.out);
    }

    public static void main(String[] args) {
        new Brute().run();
    }

    private void debug(Object...os) {
        System.err.println(Arrays.deepToString(os));
    }

    private InputReader reader;
    private PrintWriter writer;
}

class InputReader {
    InputReader(InputStream in) {
        reader    = new BufferedReader(new InputStreamReader(in));
        tokenizer = new StringTokenizer("");
    }

    private String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    public Integer nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    private BufferedReader  reader;
    private StringTokenizer tokenizer;
}

generator.py

from random import seed, randint, shuffle

ns = []
for i in xrange(20):
    ns.append(100)
for i in xrange(6):
    ns.append(1000)
for i in xrange(4):
    ns.append(100000)

if __name__ == "__main__":
    seed(0)
    print len(ns)
    for n in ns:
        print n
        splits = [0]
        for i in xrange(n):
            splits.append(randint(0, 10 ** 6))
        splits.sort()
        a = []
        for i in xrange(n):
            a.append(splits[i + 1] - splits[i])
        shuffle(a)
        print " ".join(map(str, a))

Main.java

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    public void run() {
        try {
            int testCount = reader.nextInt();
            for (int t = 1; t <= testCount; ++ t) {
                int n = reader.nextInt();
                assert 1 <= n && n <= 100000;
                int[] a = new int[n + 1];
                int sum = 0;
                for (int i = 0; i < n; ++ i) {
                    a[i] = reader.nextInt();
                    assert a[i] >= 0;
                    sum += a[i];
                }
                assert sum <= 1000000;
                for (int i = n - 1; i >= 0; -- i) {
                    a[i] += a[i + 1];
                }
                int result = 0;
                for (int k = 0; 1 << k <= sum; ++ k) {
                    int total = 0;
                    int[] values = new int[n + 1];
                    for (int i = 0; i <= n; ++ i) {
                        values[i] = a[i] % (1 << k + 1);
                    }
                    Arrays.sort(values);
                    int[] count = new int[n + 1];
                    for (int i = n; i >= 0; -- i) {
                        int s = a[i] % (1 << k + 1);
                        for (int j = binarySearch(values, s); j <= n; j += ~j & j + 1) {
                            count[j] ++;
                        }
                        total += query(values, count, s - (1 << k));
                        total += query(values, count, s + (1 << k));
                        total -= query(values, count, s);
                    }
                    result |= (total & 1) << k;
                }
                writer.println(String.format("Case #%d: %d", t, result));
            }
        } catch (IOException ex) {
            assert false;
        }
        writer.close();
    }

    int binarySearch(int[] list, int item) {
        int low = -1;
        int high = list.length - 1;
        while (low < high) {
            int middle = low + high + 1 >> 1;
            if (list[middle] <= item) {
                low = middle;
            } else {
                high = middle - 1;
            }
        }
        return low;
    }

    int query(int[] values, int[] count, int item) {
        int result = 0;
        for (int i = binarySearch(values, item); i >= 0; i -= ~i & i + 1) {
            result += count[i];
        }
        return result;
    }

    Main() {
        reader = new InputReader(System.in);
        writer = new PrintWriter(System.out);
    }

    public static void main(String[] args) {
        new Main().run();
    }

    private void debug(Object...os) {
        System.err.println(Arrays.deepToString(os));
    }

    private InputReader reader;
    private PrintWriter writer;
}

class InputReader {
    InputReader(InputStream in) {
        reader    = new BufferedReader(new InputStreamReader(in));
        tokenizer = new StringTokenizer("");
    }

    private String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    public Integer nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    private BufferedReader  reader;
    private StringTokenizer tokenizer;
}

statement.md

bobo was given a long sequence of integers ${A_1, A_2, \dots, A_N}$. Thanks to his high talent, he quickly calculated the sum of each consecutive sub-sequence. Now he would like to know the exclusive-or of the sums.

Input

The first line of the input contains an integer $T$ which is the number of test cases, and $T$ test cases follow.

For each test case, the first line contains an integer $N$. The second line contains $N$ integers $A_1, A_2, \dots, A_N$.

($1 \leq N \leq 10^5, 0 \leq A_1 + A_2 \dots + A_N \leq 10^6, A_1, A_2, \dots, A_N \geq 0$)

Output

For each test case, print a single integer which denotes the result.

Sample input

1
2
1 2

Sample output

Case #1: 0