TopCoder

Nekosyndrome
かわいいは正義!

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

23.5% (8/34)

Tags

Description

在一個由 $n \times k$ 個單位正方形排成的矩形表格上,如果某兩個格子共用一個邊,那麼我們說這兩個格子相鄰。請寫一個程式計算出有多少種方法對表格的某些格子塗上黑色,使得這個表格上的每一個小格子,都恰有一個相鄰的格子被塗上黑色。

Input Format

包含兩個以空白隔開的整數 $n,k$, $(0 < n < 500, 0 < k < 32)$。

Output Format

請輸出有多少種不同的塗色方式。

Sample Input 1

2 2

Sample Output 1

4

Hints

Problem Source

原TIOJ1264 / Bulgarian National Olympiad in Informatics 2008 Final (Prob A3)

Subtasks

No. Testdata Range Score
1 0 4
2 1 4
3 2 4
4 3 4
5 4 4
6 5 4
7 6 4
8 7 4
9 8 4
10 9 4
11 10 4
12 11 4
13 12 4
14 13 4
15 14 4
16 15 4
17 16 4
18 17 4
19 18 4
20 19 4
21 20 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
10 1000 65536 262144 11
11 1000 65536 262144 12
12 1000 65536 262144 13
13 1000 65536 262144 14
14 1000 65536 262144 15
15 1000 65536 262144 16
16 1000 65536 262144 17
17 1000 65536 262144 18
18 1000 65536 262144 19
19 1000 65536 262144 20
20 1000 65536 262144 21