XorRank | Topcoder Archive

Problem Statement

This problem is about sets of non-negative integers.

A set S is called perfect if it has the following properties:

it is non-empty
whenever a and b are two (not necessarily distinct) elements of S, the number (a xor b) is also an element of S

It can be shown that the size of any perfect set must be a power of two.

You are given an int k, and two equally-long int[]s rank and value. We are interested in perfect sets that have the following properties:

The size of the set is 2^k.
For each i, the rank[i]-th smallest number in the set (0-based index) must be value[i].

If there are infinitely many such perfect sets, return -1. Otherwise, return the number of such perfect sets, modulo (10^9 + 7).

Definition

Class:: XorRank
Method:: count
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int count(int k, int[] rank, int[] value)
(be sure your method is public)

Constraints

k will be between 1 and 30, inclusive.
rank will contain between 1 and 50 elements, inclusive.
rank and value will contain the same number of elements.
Each element in rank will be between 0 and (2^k-1), inclusive.
Each element in value will be between 0 and 1,000,000,000, inclusive.

Examples

```
2
```
```
{3}
```
```
{13}
```
```
Returns: 5
```
We want perfect sets that have 2^2 = 4 elements. The largest of those elements should be the number 13. We have 5 solutions: {0, 1, 12, 13} {0, 4, 9, 13} {0, 5, 8, 13} {0, 6, 11, 13} {0, 7, 10, 13}
```
2
```
```
{3, 1}
```
```
{13, 5}
```
```
Returns: 1
```
This time the only one is: {0, 5, 8, 13}.
```
6
```
```
{58}
```
```
{57}
```
```
Returns: 0
```
Since all numbers in the set are nonnegative (and distinct), the number with rank 58 must be at least 58. Thus, there is no solution.
```
10
```
```
{588, 588}
```
```
{1748912, 1748913}
```
```
Returns: 0
```
The 588-th number can't be both 1748912 and 1748913 at the same time.
```
1
```
```
{0}
```
```
{0}
```
```
Returns: -1
```
There are infinite number of them, like: {0,1}, {0,2}, {0,3}, ...

{1000000, 1000000, 0, 10, 1}

{449989776, 449989776, 0, 100, 1}

Returns: 863762835

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.