TopCoder Statistics - Problem Statement

Problem Statement

You have a sufficient supply of identical planks. Each plank has the shape of an 1 times H rectangle.

The floor of your room is also a rectangle. Its width is W and its height is 2H-1. You want to use the planks you have to tile the floor. The entire floor must be covered and the planks must not overlap. (The width W is guaranteed to be a multiple of H, so this is always possible.)

You are given the two ints H and W. Return the number of ways to tile the floor, modulo 1,000,000,007.

Definition

Class:: PlankTiling
Method:: sumup
Parameters:: int, int
Returns:: int
Method signature:: int sumup(int H, int W)
(be sure your method is public)

Constraints

H will be between 2 and 1000, inclusive.
W will be between 2 and 1000, inclusive.
W will be a multiple of H.

Examples

2

4

Returns: 11

We are using 1x2 planks to tile a rectangle of width 4 and height 3. There are eleven different ways to do so:
4

4

Returns: 5
3

9

Returns: 121
29

841

Returns: 193514715
2

1000

Returns: 146530309
1000

1000

Returns: 1001
2

2

Returns: 3
500

1000

Returns: 500501
3

3

Returns: 4
4

4

Returns: 5
7

7

Returns: 8
12

12

Returns: 13
19

19

Returns: 20
28

28

Returns: 29
39

39

Returns: 40
52

52

Returns: 53
67

67

Returns: 68
84

84

Returns: 85
27

27

Returns: 28
56

56

Returns: 57
91

91

Returns: 92
25

25

Returns: 26
18

18

Returns: 19
930

930

Returns: 931
919

919

Returns: 920
911

911

Returns: 912
548

548

Returns: 549
771

771

Returns: 772
685

685

Returns: 686
742

742

Returns: 743
919

919

Returns: 920
921

921

Returns: 922
913

913

Returns: 914
55

220

Returns: 57269356
129

516

Returns: 718471817
481

962

Returns: 463204
244

488

Returns: 119317
105

315

Returns: 4079356
484

968

Returns: 468997
79

553

Returns: 296493731
489

978

Returns: 478732
323

646

Returns: 208982
110

660

Returns: 979181893
473

946

Returns: 447932
417

834

Returns: 348196
218

436

Returns: 95267
31

341

Returns: 111437070
236

708

Returns: 46144373
9

702

Returns: 549086680
397

794

Returns: 315616
149

745

Returns: 565655750
286

858

Returns: 82082573
140

840

Returns: 397122151
141

987

Returns: 852517494
440

880

Returns: 387641
489

978

Returns: 478732
409

818

Returns: 334972
215

645

Returns: 34900091
137

548

Returns: 185274794
439

878

Returns: 385882
490

980

Returns: 480691
107

535

Returns: 834911150
225

450

Returns: 101476
474

948

Returns: 449827
272

816

Returns: 70618001
300

900

Returns: 94725301
323

646

Returns: 208982
54

756

Returns: 531101389
48

768

Returns: 774838811
87

174

Returns: 15226
59

767

Returns: 143957382
70

630

Returns: 356254921
53

159

Returns: 528146
81

648

Returns: 587763785
53

371

Returns: 578949677
11

429

Returns: 180201878
2

846

Returns: 305198945
94

376

Returns: 485639909
70

140

Returns: 9871
27

108

Returns: 3377728
51

102

Returns: 5254
49

735

Returns: 93484750
74

814

Returns: 497524378
14

686

Returns: 536978578
60

480

Returns: 385300480
44

352

Returns: 624317774
52

468

Returns: 416558030
36

792

Returns: 728303906

Statistics

Problem Statement for "PlankTiling"

Problem Statement

Definition

Constraints

Examples