Statistics

Problem Statement for "BearFills"

Problem Statement

Bear Limak has a rectangular grid that consist of H times W unit square cells. Limak also has N square stamps. The lengths of the stamps' sides are 2^0, 2^1, ..., 2^(N-1).

A set of stamps is called good if it can be used to cover the entire grid. Each stamp must be placed along the grid lines. I.e., for each stamp each cell is either completely covered by the stamp or not covered at all. The stamps may overlap arbitrarily. The stamps may also cover areas outside of the grid. For example, you may use a 4x4 stamp just to cover a single cell in the corner of the grid.

You are given the int N and the longs H and W. Limak wants to choose a subset of his stamps that will be good. Return the number of ways in which he can do so.

Definition

Class:
BearFills
Method:
countSets
Parameters:
int, long, long
Returns:
long
Method signature:
long countSets(int N, long W, long H)
(be sure your method is public)

Notes

  • N will be between 1 and 60, inclusive.
  • H and W will be between 1 and 10^18, inclusive.

Constraints

    Examples

    1. 3

      1

      3

      Returns: 5

      He has a 1x3 rectangle and 3 square stamps. The stamps' sides are 1, 2, and 4. The good sets of stamps are the following ones: (1,2), (1,2,4), (1,4), (2,4), and (4).

    2. 3

      3

      5

      Returns: 1

      He has a 3x5 rectangle and 3 square stamps. The stamps' sides are 1, 2, and 4. He needs all of them.

    3. 60

      3

      2

      Returns: 1152921504606846972

      He has a 3x2 rectangle and 60 square stamps. Only four sets are not good: (), (1), (2), and (1,2). The answer is 2^60-4.

    4. 6

      5

      4

      Returns: 56

    5. 1

      1

      1

      Returns: 1

      empty tests, could be changed into example

    6. 1

      1

      1

      Returns: 1

    7. 1

      1

      2

      Returns: 0

    8. 1

      1000000000000000000

      1000000000000000000

      Returns: 0

    9. 2

      1

      1

      Returns: 3

    10. 2

      1

      2

      Returns: 2

    11. 2

      2

      1

      Returns: 2

    12. 2

      3

      1

      Returns: 1

    13. 2

      1

      3

      Returns: 1

    14. 2

      2

      2

      Returns: 2

    15. 2

      2

      3

      Returns: 0

    16. 2

      500000000000000000

      333333333333333333

      Returns: 0

    17. 3

      1

      1

      Returns: 7

    18. 3

      1

      2

      Returns: 6

    19. 3

      2

      1

      Returns: 6

    20. 3

      2

      2

      Returns: 6

    21. 3

      3

      1

      Returns: 5

    22. 3

      2

      3

      Returns: 4

    23. 3

      4

      1

      Returns: 4

    24. 3

      1

      4

      Returns: 4

    25. 3

      5

      1

      Returns: 3

    26. 3

      2

      5

      Returns: 2

    27. 3

      2

      4

      Returns: 4

    28. 3

      3

      3

      Returns: 4

    29. 3

      4

      4

      Returns: 4

    30. 3

      3

      4

      Returns: 4

    31. 3

      5

      3

      Returns: 1

    32. 3

      5

      3

      Returns: 1

    33. 3

      5

      4

      Returns: 0

    34. 3

      2

      6

      Returns: 2

    35. 3

      1

      6

      Returns: 2

    36. 3

      1

      7

      Returns: 1

    37. 3

      8

      1

      Returns: 0

    38. 3

      1000000000000000000

      1

      Returns: 0

    39. 3

      7

      2

      Returns: 0

    40. 3

      5

      5

      Returns: 0

    41. 4

      2

      5

      Returns: 10

    42. 4

      6

      3

      Returns: 8

    43. 5

      5

      5

      Returns: 24

    44. 6

      10

      20

      Returns: 36

    45. 6

      8

      8

      Returns: 56

    46. 6

      8

      9

      Returns: 48

    47. 33

      24

      18

      Returns: 8589934560

    48. 33

      29

      16

      Returns: 8589934560

    49. 21

      15

      2

      Returns: 2097136

    50. 27

      28

      13

      Returns: 134217696

    51. 38

      21

      4

      Returns: 274877906920

    52. 38

      18

      6

      Returns: 274877906922

    53. 20

      22

      20

      Returns: 1048544

    54. 35

      21

      4

      Returns: 34359738344

    55. 14

      10

      12

      Returns: 16368

    56. 22

      15

      9

      Returns: 4194288

    57. 26

      786429311801

      267978931103

      Returns: 0

    58. 27

      535117610055

      502813891536

      Returns: 0

    59. 35

      629323147933

      591129520407

      Returns: 0

    60. 35

      20386284475

      314432298861

      Returns: 0

    61. 30

      801790009121

      688297105827

      Returns: 0

    62. 33

      976151277153

      680358180286

      Returns: 0

    63. 17

      482207812547

      446718819695

      Returns: 0

    64. 8

      280312875687

      745708947947

      Returns: 0

    65. 36

      732738098157

      704344264659

      Returns: 0

    66. 21

      158849910281

      860323318519

      Returns: 0

    67. 56

      525337074840097679

      450000650378937097

      Returns: 0

    68. 60

      476607361346196564

      912994317508995492

      Returns: 0

    69. 60

      439181651447323773

      257748377941753647

      Returns: 576460752303423488

    70. 56

      100858580960662041

      481675599978569609

      Returns: 0

    71. 58

      858741320719011613

      296194989764343051

      Returns: 0

    72. 59

      142924358137994538

      676986696398315125

      Returns: 0

    73. 56

      691763210211019059

      969105774245729255

      Returns: 0

    74. 58

      624256359999031729

      317525195552086015

      Returns: 0

    75. 56

      585767157804835450

      254593573631841591

      Returns: 0

    76. 58

      935811243574382823

      26770709343246610

      Returns: 0

    77. 60

      1000000000000000000

      100000000000000000

      Returns: 144115188075855872

    78. 59

      1000000000000000000

      1000000000000000000

      Returns: 0

    79. 60

      12

      4

      Returns: 1152921504606846964

    80. 60

      1000000000000000000

      1

      Returns: 152921504606846976

    81. 60

      3

      58823529411764705

      Returns: 1094097975195082269

    82. 60

      1

      1

      Returns: 1152921504606846975

    83. 60

      1

      2

      Returns: 1152921504606846974

    84. 59

      2

      1

      Returns: 576460752303423486

    85. 60

      2

      325329585832539599

      Returns: 827591918774307376

    86. 59

      288230376151711745

      288230376151711742

      Returns: 2

    87. 60

      1

      1099511627776

      Returns: 1152920405095219200

    88. 60

      1

      1000000000000000000

      Returns: 152921504606846976

    89. 60

      100000000000000000

      1000000000000000

      Returns: 1052716412897853440

    90. 11

      1030

      10

      Returns: 1010

    91. 5

      10

      58

      Returns: 0

    92. 60

      1

      1000000000000000

      Returns: 1151921504606846976

    93. 60

      13449832

      115292150460684697

      Returns: 1037629354139451392

    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: