AT_agc021_f [AGC021F] Trinity

有一个纵向 $N$ 行、横向 $M$ 列的网格。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。特别地，最左上角的格子为 $(1,1)$，最右下角的格子为 $(N,M)$。高桥君将若干（可以为 $0$ 个）格子涂成黑色，其余格子为白色。 定义长度为 $N$ 的数列 $A$，长度为 $M$ 的数列 $B$ 和 $C$，如下所示： - $A_i\ (1\leq i\leq N)$：第 $i$ 行中被涂黑的格子的最小列号 $j$（如果不存在，则为 $M+1$）。 - $B_i\ (1\leq i\leq M)$：第 $i$ 列中被涂黑的格子的最小行号 $k$（如果不存在，则为 $N+1$）。 - $C_i\ (1\leq i\leq M)$：第 $i$ 列中被涂黑的格子的最大行号 $k$（如果不存在，则为 $0$）。 请计算所有可能的三元组 $(A,B,C)$ 的数量，并对 $998244353$ 取模后输出。

输入为一行，包含两个整数 $N$ 和 $M$。

输出所有可能的 $(A,B,C)$ 组数对 $998244353$ 取模的结果。

## 注意 本题提交的源代码大小限制为 $20000$ 字节。超出该长度的提交将被判为无效，请注意。 ## 数据范围 - $1 \leq N \leq 8000$ - $1 \leq M \leq 200$ - $N,M$ 均为整数 ## 部分分 - 对于满足 $N \leq 300$ 的数据集，答对可得 $1500$ 分。 ## 样例说明 1 当 $N=2$ 时，可以由 $B_i,C_i$ 的信息唯一确定每一列黑色格子的分布。对于每个 $i$，$(B_i,C_i)$ 的组合有 $(1,1),(1,2),(2,2),(3,0)$ 共 $4$ 种，因此答案为 $4^M=64$ 种。 由 ChatGPT 4.1 翻译