XorOrderDiv1 | Topcoder Archive

Problem Statement

Welcome to the Festival of Binary Numbers! The festival will last for 2^m days. The days are numbered 0 through 2^m - 1. On each day of the festival there is a single race. There are n contestants, numbered 0 through n-1. Each contestant takes part in all 2^m races. The skill level of contestant i is a[i]. All a[i] are integers between 0 and 2^m - 1, inclusive. Additionally, all a[i] are distinct.

For each i and j, the time needed by contestant i to finish the race on day j can be computed as (a[i] xor j). Note that on each day the contestants' times will all be distinct. After each race the contestants are ordered according to the time they needed, starting with the fastest one. Contestant who places x-th (counting from zero) will get x^2 penalty points. (I.e., starting from the winner of the race, the contestants get 0, 1, 4, 9, 16, ... penalty points.) For each i, let p[i] be the total number of penalty points contestant i receives in the 2^m races. Then, let q[i] = p[i] modulo (10^9 + 7).

You are given the ints m and n. You are also given ints a0 and b. These are used to generate the sequence a, as follows: For each i, a[i] = (a0 + i * b) modulo 2^m. Constraints guarantee that the elements of a will be distinct.

Compute each of the values q[i], and return the bitwise xor of all these values.

Definition

Class:: XorOrderDiv1
Method:: get
Parameters:: int, int, int, int
Returns:: int
Method signature:: int get(int m, int n, int a0, int b)
(be sure your method is public)

Notes

The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of the allowed size within the given limits.
The author's solution does actually compute each of the values q[i].

Constraints

m will be between 1 and 30, inclusive.
n will be between 1 and 200,000, inclusive.
a0 will be between 0 and 2 ^ m - 1, inclusive.
b will be between 0 and 2 ^ m - 1, inclusive.
The values a0 and b will be such that all values of the sequence a are distinct.

Examples

```
2
```
```
3
```
```
0
```
```
1
```
```
Returns: 8
```
There are 2^2 = 4 days and 3 contestants. Their skill levels are a = {0, 1, 2}. The individual races are described below: day 0: finishing times are {0, 1, 2}, penalty points are {0, 1, 4}. day 1: finishing times are {1, 0, 3}, penalty points are {1, 0, 4}. day 2: finishing times are {2, 3, 0}, penalty points are {1, 4, 0}. day 3: finishing times are {3, 2, 1}, penalty points are {4, 1, 0}. Hence, the penalty point totals are {6, 6, 8}, and the correct return value is (6 xor 6 xor 8) = 8.
```
3
```
```
5
```
```
1
```
```
3
```
```
Returns: 48
```
The skill levels in this example are a = {1, 4, 7, 2, 5}.
```
16
```
```
100
```
```
41
```
```
5
```
```
Returns: 523436032
```
```
30
```
```
200000
```
```
399
```
```
18082016
```
```
Returns: 408585698
```
Watch out for integer overflow.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.