AT_abc196_d [ABC196D] Hanjo

题目描述

有一个纵向 $H$ 米、横向 $W$ 米的矩形房间。
现在要在这个房间里铺设 $A$ 张 $2$ 米 $\times$ $1$ 米的不可区分的榻榻米（长方形瓷砖），以及 $B$ 张 $1$ 米 $\times$ $1$ 米的不可区分的半榻榻米（正方形瓷砖）。$2$ 米 $\times$ $1$ 米的榻榻米可以竖着或横着放置。
请问有多少种不同的铺设方法？
另外，保证 $2A + B = HW$。通过旋转或翻转才能重合的铺设方式视为不同的方案。

输入格式

输入为一行，格式如下：

$H$ $W$ $A$ $B$

输出格式

输出答案。

样例 1

输入

2 2 1 2

输出

4

样例 2

输入

3 3 4 1

输出

18

样例 3

输入

4 4 8 0

输出

36

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq H, W$
• $HW \leq 16$
• $0 \leq A, B$
• $2A + B = HW$

样例解释 1

共有以下 $4$ 种方式。

样例解释 2

共有以下 $6$ 种方式，以及这些方式旋转后的方案也包含在内。

由 ChatGPT 4.1 翻译