题目内容

电影院共有 $n$ 行、$m$ 列座位。部分座位已被陌生人的购买，剩余座位为空闲。你和你的 $k$ 位朋友希望一起观影，选座时有以下要求：

只能选择空闲座位；

全部 $k$ 个人的选座需要位于同一行，且保持连续；

对于选中的每一个位置，其上下左右相邻的位置要么不存在，要么为空闲，要么同样为被你们选中的位置。

题意

给定一个 $n$ 行 $m$ 列的影院座位布局，其中 0 表示空座，1 表示已被订出。你和朋友想一起观影，且组内人员可区分。每次希望选定连续的 $k$ 个空座，中间不允许被占，且在垂直方向（上下）和水平方向（左右）相邻的位置都不能有已订座位，满足条件的方案数乘以 $k!$ 即为答案，对 $998244353$ 取模。

输入包括多次询问，每次给出一个 $k$，需要输出对应的方案数。

题解思路

枚举每行安全区间

1. 定义 safe[i][j]：仅当座位 $(i,j)$ 为空且其上下位置要么越界要么也是空时，safe[i][j]=1，否则为0。
2. 对于每一行，用前缀和 pref[j] 快速判断任意区间内是否全是 safe=1。