No.3563 No T-Junctions in Kyoto
タグ : / 解いたユーザー数 24
作問者 :
soryuusi0219
/ テスター :
みうね
fluorine
TKTYI
HoyHoyCharhang
jastaway
yaaya
butsurizuki
wasab1
tatesoto
KumaTachiRen
問題文
南北に $N$ 行、東西に $M$ 列のグリッド状に並んだ $N \times M$ 個の区画からなる京都市を、いくつかの特別区に分割します。
各特別区は東西南北に連結していなければなりません。 すなわち、同じ特別区に属する任意の 2 つの区画は、辺を共有して隣接する同区内の区画のみを辿って互いに行き来できる必要があります。
隣接する区画が異なる特別区に属する場合、その境界には区画を隔てる大通りが敷設されます。 ただし、交通渋滞を防ぐために、グリッドの内部には丁字路を作ってはいけません。すなわち、グリッド内部の任意の交差点において、そこに接続する大通りの数がちょうど $3$ 本になってはいけません。
条件を満たす特別区の分割の総数を $998244353$ で割った余りを求めてください。 ただし、2 つの分割方法は、任意の 2 つの区画に対しそれらが同じ特別区に属するかどうかが一致するとき、かつそのときに限り同一の分割とみなします。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$
- $1 \le N, M \le 3000$
- 入力はすべて整数
部分点
この問題にはサブタスクによる部分点が設定されています。
| サブタスク名 | 配点 | 制約 |
|---|---|---|
| 部分点1 | 10 点 | $N = 1$ |
| 満点 | 90 点 | 追加の制約はない |
出力
答えを $1$ 行に出力せよ。
サンプル
サンプル1
入力
2 2
出力
8
$2 \times 2$ の区画を、内部に丁字路ができないように特別区に分割する方法は以下の $8$ 通りです。
例えば以下のように3つの特別区に分割した場合、中央の交差点に集まる大通りが3本となり、丁字路ができてしまうため条件を満たしません。
サンプル2
入力
1 1
出力
1
区画が $1$ つのみであるため、分割せずに全体を $1$ つの特別区とする $1$ 通りのみです。内部に交差点が存在しないため、丁字路ができることもありません。
サンプル3
入力
2026 529
出力
996014394
$998244353$ で割った余りを求めることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。