AT_ttpc2023_i T Tile Placement Counting
题目描述
求用如图所示的覆盖 $4$ 个格子的 T 形瓷砖，将 $H$ 行 $W$ 列的网格完全铺满的方案数，答案对 $998244353$ 取模。
铺满时需要满足以下条件：
- 瓷砖必须按网格对齐放置。
- 瓷砖不得超出网格边界。
- 不同的瓷砖不能覆盖同一个格子。
- 所有格子都必须被瓷砖覆盖。
瓷砖允许旋转放置，但没有正反区分，瓷砖之间也不存在区分。另外，通过旋转或翻转完全重叠一致的铺法也视作不同的方案。
输入格式
输入从标准输入读入，格式如下：
> $H$ $W$
输出格式
输出方案数对 $998244353$ 取模后的结果。
说明/提示
### 样例解释 1
有 $2$ 种铺设方案，如下图所示。
### 样例解释 2
有可能无法铺满网格。
### 样例解释 3
请输出结果对 $998244353$ 取模的值。
### 数据范围
- 输入均为整数
- $1 \leq H \leq 30$
- $1 \leq W \leq 10^{18}$
由 ChatGPT 5 翻译