XorSequence | Topcoder Archive

Problem Statement

You are given an integer sequence A and an int N that is a power of 2. All elements of A are between 0 and N-1, inclusive.

You can now choose an integer B which is between 0 and N-1, inclusive. This integer determines a new sequence C defined as follows: For each valid i, C[i] = (A[i] xor B).

Given the sequence C, we will count the pairs of indices (i,j) such that both i<j and C[i]<C[j]. Compute and return the largest result we can obtain.

You are given the int N. You are also given ints sz, A0, A1, P, Q, and R. Use the following pseudocode to generate the sequence A:

A[0] = A0;
A[1] = A1;
for (i = 2; i &lt; sz; i++) {
    A[i] = (A[i - 2] * P + A[i - 1] * Q + R) modulo N;
}

Definition

Class:: XorSequence
Method:: getmax
Parameters:: int, int, int, int, int, int, int
Returns:: long
Method signature:: long getmax(int N, int sz, int A0, int A1, int P, int Q, int R)
(be sure your method is public)

Notes

Watch out for integer overflow when generating the sequence A.

Constraints

N will be between 2 and 1,073,741,824 (2^30), inclusive.
N will be a power of 2.
sz will be between 2 and 131,072, inclusive.
A0 will be between 0 and N-1, inclusive.
A1 will be between 0 and N-1, inclusive.
P will be between 0 and N-1, inclusive.
Q will be between 0 and N-1, inclusive.
R will be between 0 and N-1, inclusive.

Examples

```
4
```
```
6
```
```
3
```
```
2
```
```
0
```
```
1
```
```
3
```
```
Returns: 8
```
Using the provided pseudocode you should compute that A={3,2,1,0,3,2}. For B=3 we then get C={0,1,2,3,0,1}. For this C there are 8 pairs (i,j) such that i<j and C[i]<C[j]. These are the 8 pairs: (0,1), (0,2), (0,3), (0,5), (1,2), (1,3), (2,3), and (4,5). No other choice of B produces more than 8 pairs.
```
8
```
```
8
```
```
2
```
```
5
```
```
3
```
```
1
```
```
4
```
```
Returns: 13
```
A={2,5,7,2,3,5,2,5}.
```
8
```
```
7
```
```
3
```
```
0
```
```
1
```
```
2
```
```
4
```
```
Returns: 12
```
A={3,0,7,2,7,4,3}.
```
32
```
```
15
```
```
7
```
```
9
```
```
11
```
```
2
```
```
1
```
```
Returns: 60
```
A={7,9,0,4,9,31,2,26,11,21,4,16,13,11,6}.
```
131072
```
```
131072
```
```
7
```
```
7
```
```
1
```
```
0
```
```
0
```
```
Returns: 0
```
All elements of A are equal to 7. Regardless of the value of B you choose, all elements in C will be equal as well. Thus, the number of pairs we seek is always zero.

Returns: 4302679760

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.