Problem Statement
Time limit: 5 seconds.
You have an R times C rectangle divided into unit squares.
You want to perform a sequence of two actions.
The first action is to remove some collection of individual unit squares. (All remaining squares are left in their original positions.
The second action is to perfectly tile all the remaining squares using horizontally and/or vertically placed 1x2 dominoes.
Consider all possible ways of correctly performing these two actions. Among them, count all possible ways to perform the first action. Return that count modulo 1,000,000,007.
Definition
- Class:
- CountTilings
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int R, int C)
- (be sure your method is public)
Notes
- In a perfect tiling of a collection of squares each 1x2 domino tile covers two squares, and each square is covered by exactly one domino.
Constraints
- R will be between 1 and 8, inclusive.
- If R = 8, C will be between 1 and 200, inclusive.
- If R = 7, C will be between 1 and 1,000, inclusive.
- If R <= 6, C will be between 1 and 8,000, inclusive.
Examples
1
1
Returns: 1
As your first action you must remove the only square. For your second action you are then left with an empty set of squares, and that can be perfectly tiled using an empty set of dominoes.
2
3
Returns: 18
There are 18 valid ways to perform the first action. All of them are shown below, using 'x' for a square you remove and '.' for a square you keep. xxx xxx xx. x.x .xx ..x x.. xxx xxx xx. x.x .xx xxx xxx ..x x.. ..x .x. x.. x.. ..x xx. .xx ... ... ..x .x. x.. ..x x.. ... ... xx. .xx ... ... Note that for some of these there are multiple valid ways to perform the second action. That has no impact on our answer, each of the options shown above is only counted once.
1
50
Returns: 365010934
For a 1xC strip we are essentially just tiling it with 1x1 and 1x2 tiles. The numbers of such tilings are clearly Fibonacci numbers. The exact number of tilings for C = 50 is F[51] = 20,365,011,074.
1
2
Returns: 2
1
3
Returns: 3
1
4
Returns: 5
1
7
Returns: 21
1
12
Returns: 233
2
1
Returns: 2
3
1
Returns: 3
4
1
Returns: 5
8
1
Returns: 34
2
2
Returns: 6
2
4
Returns: 54
2
5
Returns: 162
2
6
Returns: 486
2
7
Returns: 1458
2
8
Returns: 4374
2
9
Returns: 13122
2
10
Returns: 39366
2
11
Returns: 118098
2
12
Returns: 354294
2
13
Returns: 1062882
2
14
Returns: 3188646
3
2
Returns: 18
3
3
Returns: 98
3
4
Returns: 550
3
5
Returns: 3054
3
6
Returns: 17014
3
7
Returns: 94682
3
8
Returns: 527086
3
9
Returns: 2933902
4
2
Returns: 54
4
3
Returns: 550
4
4
Returns: 5700
4
5
Returns: 58830
4
6
Returns: 607752
4
7
Returns: 6276966
5
2
Returns: 162
5
3
Returns: 3054
5
4
Returns: 58830
5
5
Returns: 1125703
6
2
Returns: 486
6
3
Returns: 17014
6
4
Returns: 607752
7
2
Returns: 1458
7
3
Returns: 94682
7
4
Returns: 6276966
8
2
Returns: 4374
8
3
Returns: 527086
6
198
Returns: 757855121
3
178
Returns: 142373929
6
140
Returns: 400117503
7
200
Returns: 76820147
3
196
Returns: 798243119
5
190
Returns: 831501210
7
166
Returns: 300638278
8
198
Returns: 81721241
8
195
Returns: 748384129
3
150
Returns: 252047761
2
197
Returns: 176205388
1
195
Returns: 158879092
4
103
Returns: 235066220
2
200
Returns: 757545448
7
196
Returns: 672168915
6
200
Returns: 287744010
1
155
Returns: 453204199
7
193
Returns: 675016939
3
198
Returns: 143555643
1
170
Returns: 540401498
4
200
Returns: 834645531
8
130
Returns: 96665849
6
172
Returns: 234939633
1
191
Returns: 762791999
2
132
Returns: 436703975
8
200
Returns: 789118743
8
156
Returns: 492075730
1
200
Returns: 529309711
2
199
Returns: 585848485
5
161
Returns: 794729464
6
190
Returns: 722538700
4
184
Returns: 815465933
4
190
Returns: 801954016
4
196
Returns: 581747554
5
191
Returns: 835217659
5
133
Returns: 491290472
3
200
Returns: 97443836
5
200
Returns: 436376943
7
130
Returns: 135055965
2
143
Returns: 798517805
7
972
Returns: 420683059
4
5043
Returns: 585080251
1
6514
Returns: 996575932
5
7982
Returns: 997365554
5
2942
Returns: 437807021
6
7837
Returns: 540162958
6
6815
Returns: 715642674
4
1885
Returns: 580311472
5
8000
Returns: 977740233
1
6
Returns: 13
3
4650
Returns: 34160780
6
7986
Returns: 38067925
4
7846
Returns: 360877698
4
5930
Returns: 56403070
4
5396
Returns: 76377844
2
273
Returns: 351793935
5
3066
Returns: 169774566
1
7843
Returns: 65252484
7
891
Returns: 911324946
6
7979
Returns: 112786267
2
4287
Returns: 942399642
5
7974
Returns: 179726845
6
8000
Returns: 464509049
7
860
Returns: 676358534
5
75
Returns: 218811564
7
1000
Returns: 973101978
7
954
Returns: 524749248
3
7723
Returns: 197272297