F - Hanjo 2

Contest Duration: 2021-06-06(Sun) 12:00 - 2021-06-06(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Hanjo 2 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

縦 $H$ メートル、横 $W$ メートルの長方形の部屋があります。
この部屋に $2$ メートル × $1$ メートルの区別できない畳 (長方形のタイル) と、 $1$ メートル × $1$ メートルの区別できない半畳 (正方形のタイル) を敷き詰めます。 $2$ メートル × $1$ メートルの畳は縦長にも横長にも使うことができます。
敷き詰める方法は何通りあるでしょうか？
回転や反転を行うことで初めて一致するような敷き詰め方は区別します。

答えは非常に大きくなる可能性があるので $998244353$ で割ったあまりを求めてください。

制約

$1 \leq H \leq 6$
$1 \leq W \leq 10^{12}$

入力

入力は以下の形式で標準入力から与えられる。

 $H$   $W$

出力

答えを出力せよ。

入力例 1Copy

Copy

2 2

出力例 1Copy

Copy

以下の $7$ つです。

入力例 2Copy

Copy

3 3

出力例 2Copy

Copy

入力例 3Copy

Copy

5 100

出力例 3Copy

Copy

379944232

$998244353$ で割ったあまりを求めてください。

Score : $600$ points

Problem Statement

We have a rectangular room that is $H$ meters long and $W$ meters wide.
We will fill this entire room with tatami (rectangular mats) that are $2$ meters long and $1$ meter wide, and hanjo (square mats) that are $1$ meter long and $1$ meter wide. Each tatami can be placed vertically or horizontally.
How many ways are there to fill the room?
We distinguish ways that match only after rotation or reflection.

Since the count can be enormous, find it modulo $998244353$ .

Constraints

$1 \leq H \leq 6$
$1 \leq W \leq 10^{12}$

Input

Input is given from Standard Input in the following format:

 $H$   $W$

Output

Print the answer.

Sample Input 1Copy

Copy

2 2

Sample Output 1Copy

Copy

We have the following seven ways:

Sample Input 2Copy

Copy

3 3

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

5 100

Sample Output 3Copy

Copy

379944232

Be sure to find the count modulo $998244353$ .