Statistics

Problem Statement for "PuyoPuyo"

Problem Statement

Cat Taro is playing a game called PuyoPuyo. In this game, he uses 4 types of colored balls called Puyos (Red, Blue, Green and Yellow) and a cylinder. He pushes Puyos into the cylinder. When he pushes a Puyo into the cylinder, it falls on top of the topmost Puyo already in the cylinder (it falls to the bottom of the cylinder if it's empty). If the cylinder contains at least L Puyos and the topmost L Puyos are the same type, the topmost L Puyos disappear.

Initially the cylinder is empty. Return the number of different ways to push N Puyos into the cylinder, so that the cylinder becomes empty after the pushes, modulo 1,000,000,007.

Definition

Class:
PuyoPuyo
Method:
theCount
Parameters:
int, int
Returns:
int
Method signature:
int theCount(int L, int N)
(be sure your method is public)

Notes

  • Two ways are different if there exists an i such that i-th pushed ball is different in one way than it is in the other.

Constraints

  • L will be between 2 and 10, inclusive.
  • N will be between 1 and 1000, inclusive.

Examples

  1. 2

    2

    Returns: 4

    He must push the same type of Puyos twice.

  2. 2

    4

    Returns: 28

    There are 4 ways to push Puyos of the form "XXXX". There are 12 ways to push Puyos of the form "XXYY". There are 12 ways to push Puyos of the form "XYYX". In this case, the cylinder changes as follows: (right represents the top of the cylinder) "" (initially the cylinder is empty) "X" (push X-type Puyo) "XY" (push Y-type Puyo) "XYY" (push Y-type Puyo) "X" (two topmost Y-type Puyos disappear) "XX" (push X-type Puyo) "" (two topmost X-type Puyos disappear) In total, there are 4 + 12 + 12 = 28 ways.

  3. 2

    58

    Returns: 868294620

  4. 4

    84

    Returns: 621871151

  5. 5

    8

    Returns: 0

  6. 2

    1000

    Returns: 36859875

  7. 2

    998

    Returns: 30389435

  8. 3

    3

    Returns: 4

  9. 3

    6

    Returns: 40

  10. 3

    999

    Returns: 86778821

  11. 3

    996

    Returns: 463701982

  12. 4

    4

    Returns: 4

  13. 4

    8

    Returns: 52

  14. 4

    1000

    Returns: 148756394

  15. 4

    996

    Returns: 232660629

  16. 5

    5

    Returns: 4

  17. 5

    10

    Returns: 64

  18. 5

    1000

    Returns: 289673403

  19. 5

    995

    Returns: 923075924

  20. 6

    6

    Returns: 4

  21. 6

    12

    Returns: 76

  22. 6

    996

    Returns: 487966164

  23. 6

    990

    Returns: 269862352

  24. 7

    7

    Returns: 4

  25. 7

    14

    Returns: 88

  26. 7

    994

    Returns: 819953526

  27. 7

    987

    Returns: 37905267

  28. 8

    8

    Returns: 4

  29. 8

    16

    Returns: 100

  30. 8

    1000

    Returns: 163819294

  31. 8

    992

    Returns: 124458741

  32. 9

    9

    Returns: 4

  33. 9

    18

    Returns: 112

  34. 9

    999

    Returns: 681002927

  35. 9

    990

    Returns: 722331324

  36. 10

    10

    Returns: 4

  37. 10

    20

    Returns: 124

  38. 10

    1000

    Returns: 61125483

  39. 10

    990

    Returns: 417012356

  40. 7

    649

    Returns: 0

  41. 5

    432

    Returns: 0

  42. 5

    38

    Returns: 0

  43. 7

    416

    Returns: 0

  44. 8

    626

    Returns: 0

  45. 2

    647

    Returns: 0

  46. 7

    445

    Returns: 0

  47. 7

    409

    Returns: 0

  48. 10

    762

    Returns: 0

  49. 8

    189

    Returns: 0

  50. 10

    1

    Returns: 0

  51. 10

    999

    Returns: 0

  52. 10

    500

    Returns: 306689442

  53. 2

    50

    Returns: 227044376

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: