Description

给一个 \(a \times b\) 矩形, 由 \(a \times b\) 个单位正方形组成. 你需要沿着网格线把它 分成分空的两部分, 每部分所有格子连通, 且至少有一个格子在原矩形的边界上. “连通” 是指任两个格子都可以通过水平或者竖直路径连在一起. 求方案总数. 例如 \(3 \times 2\) 的矩形有 \(15\) 种方案.

Input

输入仅一行, 为两个整数 \(a, b\).

Output

输出仅一行, 即方案总数.

Sample Input

3 2

Sample Output

15

Data Range

50% 的数据满足:\(1 \leq a \leq 4, 2 \leq b \leq 5\)

100% 的数据满足:\(1 \leq a \leq 6, 2 \leq b \leq 7\)

Explanation

为什么这道题给人一种提交答案题的冲动 (233)

所以就拷过来一个交表的代码直接交上去 (呵呵)

但是我们想到了一个正解: 将图分成两部分 (时间复杂度为 \(O(2^{\frac{a \cdot b}{2}})\) 然后分别暴力, 枚举上面的一半接触边框与不接触边框的、联通和不联通的共 \(4\) 种情况, 然后对于中间某一个共同行的不超过 \(2^a\) 种状态的状态来枚举, 跑一下乘法原理就可以了.

这样总的时间复杂度应该是 \(O(2^{\frac{a \cdot b}{2}} + 2^{2a})\), 算下来大概还是可以过的.

似乎这个神奇的玩意儿就叫插头 DP (没写, 觉得没意义)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

int n, m;

#include <cstdio>
#include <cstring>
#include <cstdlib>

int res[7][8] = {
    { 0, 0, 0, 0,  0,   0,     0,       0        },
    { 0, 0, 1, 2,  3,   4,     5,       6        },
    { 0, 0, 6, 15, 28,  45,    66,      91       },
    { 0, 0, 0, 52, 143, 350,   799,     1744     },
    { 0, 0, 0, 0,  614, 2431,  9184,    33603    },
    { 0, 0, 0, 0,  0,   16000, 102147,  637330   },
    { 0, 0, 0, 0,  0,   0,     1114394, 11948355 }
};

int main(int argc, char** argv)
{
    // n rows, m columns.
    scanf("%d%d", &n, &m);
    // Beginning brute-force searching.
    if (n > m) swap(n, m);
    printf("%d\n", res[n][m]);
    return 0;
}