Statistics

Problem Statement for "YetAnotherNim"

Problem Statement

Alice and Bob are playing a famous game called Nim. In this game, they first set up n piles of stones. The piles are labeled 1 through n. For each i, the number of stones on the i-th pile is between 1 and m, inclusive. Once the piles are set up, Alice and Bob alternate in taking turns. In their turn, each player chooses one of the piles and removes some stones from the pile (at least one, possibly all of them). The game ends when all piles are empty. The player unable to make a valid move loses. (In other words, the player who removed the very last stone wins.)

Since Alice and Bob are both brilliant, they soon learned how to play Nim and both started playing it optimally. Nowadays, they don't even need to play the game. They simply look at the initial setup of piles and compute who will win the game. It is no surprise that this gets a bit boring after some time.

Therefore they came up with an improved version of the game. The new version looks as follows:

  1. They both agree on the values n, m (with meanings as mentioned above), and k (explained below). For convenience, m+1 will always be a power of 2.
  2. Alice picks the sizes of the n piles.
  3. Bob selects exactly k consecutive piles and throws the remaining piles away. That is, for some i, Bob selects the piles i through i+k-1.
  4. Alice may remove some of the piles. (She is allowed to remove as many as she wants, but not all of them. She is allowed to remove no piles. The piles she removes do not have to be consecutive.)
  5. With the remaining piles Bob and Alice play a game of Nim. In this game, Bob takes the first turn.

Alice wants to win the game. Clearly, the key to winning the game is picking a good sequence of pile sizes in the second step of the above description. You are given the ints n, m, and k. Your goal is to count all sequences of pile sizes with the following property: If Alice picks the sequence in step 2, and then both Alice and Bob play the rest of the game optimally, Alice will win. As this count can be a huge number, return its remainder modulo 1,000,000,007.

Definition

Class:
YetAnotherNim
Method:
solve
Parameters:
int, int, int
Returns:
int
Method signature:
int solve(int n, int m, int k)
(be sure your method is public)

Notes

  • Two sequences of pile sizes are considered different if there is some i such that the number of stones on the i-th pile differs. For example, the sequences (2,5,7) and (2,7,5) are considered different.

Constraints

  • n will be between 1 and 1,000,000,000 (10^9), inclusive.
  • m will be between 1 and 1,000,000,000 (10^9), inclusive.
  • m + 1 will be a power of 2.
  • k will be between 1 and n, inclusive.

Examples

  1. 100

    1

    30

    Returns: 1

    There is only one valid setup: 100 piles with one stone each. In step 3, Bob will select exactly 30 of these piles. (It does not matter which 30, as they all look the same.) In step 4, Alice will remove 28 of them, leaving Bob with two piles, each with one stone. In the game of Nim, Bob takes one of the stones, Alice the other one, and she wins. Hence there is one setup such that Alice wins the game.

  2. 100

    15

    1

    Returns: 0

    Regardless of what Alice does in step 2, after step 3 there will only be one pile of stones. Nothing will happen in step 4, as Alice has to leave at least one pile of stones. In the game of Nim, Bob will simply take all the stones from that pile and win the game. So there are no setups such that Alice wins.

  3. 100

    15

    2

    Returns: 15

    In step 3, Bob will pick two of the 100 piles. Alice cannot throw anything away in step 4, because if she does, only one pile will remain and Bob easily wins the game of Nim. So the game of Nim will be played with the two piles Bob selected. Bob wins the game of Nim if and only if the piles have different sizes. So in order to win the game, Alice has to make sure that Bob picks two equal piles in step 3. The only way to force this is by choosing the same size for each of the 100 piles in step 2. As the maximal pile size is 15, there are exactly 15 winning setups.

  4. 1

    1

    1

    Returns: 0

  5. 100

    31

    10

    Returns: 908629681

  6. 3

    1

    2

    Returns: 1

  7. 7

    7

    2

    Returns: 7

  8. 7

    7

    3

    Returns: 45871

  9. 7

    7

    4

    Returns: 823543

  10. 6

    15

    2

    Returns: 15

  11. 6

    15

    3

    Returns: 141345

  12. 6

    15

    4

    Returns: 3266145

  13. 5

    15

    5

    Returns: 759375

  14. 4

    31

    3

    Returns: 38161

  15. 5

    31

    5

    Returns: 18629791

  16. 1000000000

    536870911

    1000000000

    Returns: 554016139

  17. 807

    2047

    2

    Returns: 2047

  18. 927

    4194303

    20

    Returns: 227296159

  19. 937

    65535

    15

    Returns: 289607433

  20. 242

    134217727

    9

    Returns: 848741703

  21. 979

    255

    6

    Returns: 367946486

  22. 35

    127

    7

    Returns: 69701504

  23. 200

    15

    4

    Returns: 913192763

  24. 1000

    67108863

    16

    Returns: 202537087

  25. 233

    16383

    11

    Returns: 70716866

  26. 490

    536870911

    4

    Returns: 393239975

  27. 848

    16777215

    25

    Returns: 657739813

  28. 446

    268435455

    8

    Returns: 396692399

  29. 722

    15

    4

    Returns: 384730415

  30. 164

    2047

    11

    Returns: 266179053

  31. 52

    1023

    1

    Returns: 0

  32. 49

    262143

    4

    Returns: 273319755

  33. 864

    8191

    10

    Returns: 711096398

  34. 397

    65535

    16

    Returns: 146475542

  35. 55

    127

    1

    Returns: 0

  36. 922

    1023

    5

    Returns: 989321273

  37. 427

    31

    6

    Returns: 369562211

  38. 178

    16383

    11

    Returns: 462641558

  39. 387

    16383

    6

    Returns: 401186825

  40. 53

    536870911

    2

    Returns: 536870911

  41. 387

    32767

    2

    Returns: 32767

  42. 432

    8388607

    18

    Returns: 723096285

  43. 564

    67108863

    14

    Returns: 114467885

  44. 165

    3

    3

    Returns: 716743420

  45. 161

    65535

    16

    Returns: 896575854

  46. 761

    8388607

    14

    Returns: 841863993

  47. 939874773

    31

    2

    Returns: 31

  48. 655785007

    7

    2

    Returns: 7

  49. 806389387

    127

    8

    Returns: 447041523

  50. 441336554

    536870911

    8

    Returns: 11209672

  51. 903671045

    131071

    3

    Returns: 239191909

  52. 844103894

    134217727

    2

    Returns: 134217727

  53. 541377135

    511

    2

    Returns: 511

  54. 206747615

    15

    5

    Returns: 763077455

  55. 413219686

    268435455

    27

    Returns: 430924353

  56. 817197580

    65535

    15

    Returns: 372545783

  57. 900893489

    63

    2

    Returns: 63

  58. 160260614

    511

    8

    Returns: 143978235

  59. 761892696

    127

    5

    Returns: 597537424

  60. 193333863

    536870911

    29

    Returns: 660522816

  61. 871804575

    268435455

    6

    Returns: 686161804

  62. 663156235

    15

    2

    Returns: 15

  63. 21802245

    63

    7

    Returns: 118874939

  64. 29213466

    1023

    9

    Returns: 910169708

  65. 780655648

    1

    2

    Returns: 1

  66. 61944491

    255

    6

    Returns: 427788409

  67. 999999378

    2047

    8

    Returns: 926639461

  68. 999999534

    8191

    2

    Returns: 8191

  69. 999999095

    2097151

    20

    Returns: 745737114

  70. 999999027

    524287

    3

    Returns: 827289495

  71. 999999925

    2047

    4

    Returns: 634727733

  72. 999999699

    15

    5

    Returns: 137619251

  73. 999999623

    524287

    16

    Returns: 681329474

  74. 999999782

    32767

    5

    Returns: 525033171

  75. 999999658

    8388607

    8

    Returns: 275234009

  76. 999999093

    2097151

    16

    Returns: 235701373

  77. 999999973

    1

    1

    Returns: 0

  78. 999999878

    67108863

    22

    Returns: 958037419

  79. 999999745

    536870911

    22

    Returns: 644624110

  80. 999999890

    15

    3

    Returns: 754281722

  81. 999999055

    16777215

    22

    Returns: 865267474

  82. 999999196

    1048575

    2

    Returns: 1048575

  83. 999999067

    2047

    7

    Returns: 911443105

  84. 999999180

    67108863

    22

    Returns: 477112898

  85. 999999920

    2047

    12

    Returns: 756756626

  86. 999999952

    4194303

    2

    Returns: 4194303

  87. 28

    524287

    17

    Returns: 810747637

  88. 577

    33554431

    480

    Returns: 758245158

  89. 757

    1

    272

    Returns: 1

  90. 671

    4095

    286

    Returns: 994445065

  91. 497

    16383

    76

    Returns: 842098609

  92. 773

    4194303

    104

    Returns: 798593237

  93. 140

    33554431

    25

    Returns: 475586454

  94. 393

    3

    77

    Returns: 907169137

  95. 269

    262143

    194

    Returns: 612134021

  96. 320

    67108863

    198

    Returns: 424692660

  97. 462803028

    524287

    43425601

    Returns: 310808341

  98. 403164577

    33554431

    22085480

    Returns: 87908768

  99. 129709757

    1

    11902950

    Returns: 1

  100. 260093671

    4095

    38390349

    Returns: 863354501

  101. 832379497

    16383

    371635305

    Returns: 599984760

  102. 800041773

    4194303

    64728032

    Returns: 308231999

  103. 649302140

    33554431

    497725865

    Returns: 374913849

  104. 310039393

    3

    229522960

    Returns: 87473774

  105. 296103269

    262143

    74214984

    Returns: 219145221

  106. 599463320

    67108863

    1514838

    Returns: 298857513

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: