#P16259. [Noi2026赛前集训]study学习

    ID: 15470 传统题 3000ms 1024MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>CF2500省选/NOI-奇偶性分析双射计数独立集状压 DP计数 DP分治算法滚动数组

[Noi2026赛前集训]study学习

题目背景

马上就要 NOI 了,小 A 觉得学习太累,决定玩会游戏放松一下。

这个游戏的规则如下:你有一个 n×mn\times m 的网格图,里面初始有若干两两不相邻的小怪和 Boss。你要往所有空位放置两两不相邻的黑棋和白棋。一个小怪周围必须全是黑棋和白棋,而 Boss 周围必须全是黑棋(因为黑棋会爆炸)。

小 A 随手一放就拿下了这个游戏,但他并不满足于此。他想知道,对所有能够放满棋子并符合条件的初始图,将棋子放置方案数求和后,对 998244353998244353 取模的结果。

题目描述

形式化地说,给定 n,mn,m,求满足以下条件的二维数组 aa 的数量:

  • 对任意 1≤i≤n1\le i\le n、1≤j≤m1\le j\le m,有

    ai,j∈{1,2,3,4};a_{i,j}\in\{1,2,3,4\};
  • 对任意 1≤i<n1\le i<n、1≤j≤m1\le j\le m,有

    ∣ai,j−ai+1,j∣=1;\left|a_{i,j}-a_{i+1,j}\right|=1;
  • 对任意 1≤i≤n1\le i\le n、1≤j<m1\le j<m,有

    ∣ai,j−ai,j+1∣=1.\left|a_{i,j}-a_{i,j+1}\right|=1.

答案对 998244353998244353 取模。

输入格式

一行输入两个整数 n,mn,m。

输出格式

输出一行一个整数,表示答案。

样例 1

输入

2 1

输出

6

样例 2

输入

10 7

输出

657297226

样例 3

输入

20 2

输出

109216786

数据范围

对于所有数据:

1≤n,m≤24.1\le n,m\le 24.
子任务编号 分值 n≤n\le m≤m\le
1 10 3
2 20 10
3 10 20 5
4 50 20
5 10 24