AT_arc202_b [ARC202B] Japanese "Knight's Tour"
题目描述
有一个 $H$ 行 $W$ 列的将棋棋盘,还有一个桂马棋子。令 $(i-1,j-1)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。(注意值被改变了 $1$)。
棋盘是一个环面,意味着上面和下面是连通的,左边和右边是连通的。位于 $(i,j)$ 的桂马可以移动到 $((i-2)\bmod H,(j-1)\bmod W)$ 或 $((i-2)\bmod H,(j+1)\bmod W)$。
满足以下条件的对桂马的移动称做**巡游**。
- 初始时将桂马放在 $(0,0)$。然后,移动桂马 $H\times W$ 使得桂马到达每个格子恰一次。最终桂马回到 $(0,0)$。
求不同的巡游的个数,对 $998244353$ 取模。两个巡游不同当且仅当存在一个整数 $i(1\le i\le H\times W)$,第 $i$ 次移动到达的格子不同。
输入格式
一行两个整数 $H,W$。
输出格式
一行一个整数,表示不同巡游的个数对 $998244353$ 取模的结果。
说明/提示
**数据范围**
- $3\le H\le 2\times 10^5$
- $3\le W\le 2\times 10^5$
- 输入均为整数。
**样例 1 解释**
$(0,0)\to (1,1)\to (2,2)\to (0,1)\to(1,2)\to(2,0)\to(0,2)\to(1,0)\to(2,1)\to (0,0)$ 是满足条件的一个巡游。
总共有六种不同的巡游。