Statistics

Problem Statement for "XorOrderDiv1"

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

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

  2. 3

    5

    1

    3

    Returns: 48

    The skill levels in this example are a = {1, 4, 7, 2, 5}.

  3. 16

    100

    41

    5

    Returns: 523436032

  4. 30

    200000

    399

    18082016

    Returns: 408585698

    Watch out for integer overflow.

  5. 4

    4

    13

    4

    Returns: 0

  6. 4

    16

    11

    1

    Returns: 0

  7. 14

    3468

    8468

    9295

    Returns: 376832

  8. 10

    1024

    49

    295

    Returns: 0

  9. 18

    22609

    29139

    60583

    Returns: 90578606

  10. 8

    256

    243

    189

    Returns: 0

  11. 1

    2

    1

    1

    Returns: 0

  12. 25

    181131

    6100874

    32538901

    Returns: 565078323

  13. 11

    256

    1782

    1624

    Returns: 0

  14. 6

    32

    19

    30

    Returns: 0

  15. 1

    2

    0

    1

    Returns: 0

  16. 2

    4

    3

    1

    Returns: 0

  17. 3

    8

    3

    3

    Returns: 0

  18. 4

    16

    9

    13

    Returns: 0

  19. 5

    32

    6

    31

    Returns: 0

  20. 6

    64

    60

    57

    Returns: 0

  21. 7

    128

    3

    71

    Returns: 0

  22. 8

    256

    200

    253

    Returns: 0

  23. 9

    512

    315

    259

    Returns: 0

  24. 10

    1024

    694

    975

    Returns: 0

  25. 11

    2048

    1124

    625

    Returns: 0

  26. 12

    4096

    3224

    3595

    Returns: 0

  27. 13

    8192

    7824

    6553

    Returns: 0

  28. 14

    16384

    2312

    15177

    Returns: 0

  29. 15

    32768

    7404

    4077

    Returns: 0

  30. 16

    65536

    64434

    55597

    Returns: 0

  31. 17

    131072

    99687

    68333

    Returns: 0

  32. 18

    200000

    120311

    244627

    Returns: 189170844

  33. 19

    200000

    169784

    330431

    Returns: 395242833

  34. 20

    200000

    474764

    114359

    Returns: 1015461928

  35. 21

    200000

    1344349

    1306547

    Returns: 734684794

  36. 22

    200000

    748064

    215515

    Returns: 756132988

  37. 23

    200000

    197144

    6276103

    Returns: 569417406

  38. 24

    200000

    11170183

    14874509

    Returns: 710865159

  39. 25

    200000

    22986585

    29333925

    Returns: 8479178

  40. 26

    200000

    29852808

    42214081

    Returns: 441836745

  41. 27

    200000

    123557417

    107943339

    Returns: 1036886543

  42. 28

    200000

    195798745

    25333061

    Returns: 874731109

  43. 29

    200000

    184630253

    68467457

    Returns: 692160725

  44. 30

    200000

    999386339

    419624659

    Returns: 885775293

  45. 30

    200000

    652586437

    441545291

    Returns: 105624377

  46. 30

    200000

    354881185

    58028589

    Returns: 975831528

  47. 30

    200000

    773360892

    302429889

    Returns: 715487447

  48. 30

    200000

    4679503

    1069531013

    Returns: 130547374

  49. 30

    200000

    507632453

    512108615

    Returns: 493394769

  50. 30

    200000

    50070249

    561615783

    Returns: 617558481

  51. 30

    200000

    185723516

    634447399

    Returns: 830028349

  52. 30

    200000

    134224758

    974316017

    Returns: 31260965

  53. 30

    200000

    189411711

    173158105

    Returns: 916933531

  54. 30

    200000

    857627407

    90884391

    Returns: 97933828

  55. 30

    512

    260097394

    1029701632

    Returns: 0

  56. 30

    131072

    209664784

    309387264

    Returns: 0

  57. 30

    32

    729639006

    301989888

    Returns: 0

  58. 30

    1024

    955882964

    764411904

    Returns: 0

  59. 30

    200000

    324628893

    976623008

    Returns: 567616820

  60. 30

    131072

    218538542

    264019968

    Returns: 0

  61. 30

    1

    1015705610

    0

    Returns: 0

  62. 30

    200000

    82187511

    547518544

    Returns: 1028902182

  63. 30

    200000

    213571234

    1070520

    Returns: 62956337

  64. 30

    200000

    680370295

    158469008

    Returns: 128972968

  65. 30

    1

    211943777

    10

    Returns: 0

  66. 30

    200000

    1201

    123457

    Returns: 369043401

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.
This problem was used for: