题意

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

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

题解思路

枚举每行安全区间

1. 定义 safe[i][j]：仅当座位 $(i,j)$ 为空且其上下位置要么越界要么也是空时，safe[i][j]=1，否则为0。
2. 对于每一行，用前缀和 pref[j] 快速判断任意区间内是否全是 safe=1。
3. 枚举长度 $k$，对每行滑动窗口判断区间 $[j,j+k-1]$：
   • 区间内全为安全位：pref[j+k]-pref[j]==k。
   • 区间左右相邻横向位置（若存在）都不是已订座（a[i][j-1] 和 a[i][j+k] 不为 1）。
4. 统计所有行符合条件的区间总数 cnt[k]。
5. 答案为 cnt[k] * k! % MOD。

复杂度分析

• 枚举每行：$O(n)$
• 每行构造前缀和：$O(m)$
• 对每个 $k\le\min(m,\max k)$ 遍历起点：最坏 $O(m)$
• 总体：$O(n \times m$$\times \min(m,\max k))$
• 额外预处理阶乘 $O(\max k)$，均在 $n,m,q\le100$ 约束内可接受。

代码实现

Python 代码

import sys
input = sys.stdin.readline
MOD = 998244353

def main():
    n, m, q = map(int, input().split())
    a = []
    # 读入座位矩阵
    for _ in range(n):
        line = input().strip().split()
        if len(line) == m:
            row = list(map(int, line))
        else:
            # 连续字符
            row = list(map(int, list(line[0])))
        a.append(row)

    # 读入所有查询
    qs = list(map(int, input().split()))
    maxk = max(qs)

    # 预处理阶乘
    fac = [1] * (maxk + 1)
    for i in range(1, maxk+1):
        fac[i] = fac[i-1] * i % MOD

    # 构造 safe 数组
    safe = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if a[i][j] == 0:
                ok = True
                if i>0 and a[i-1][j]==1: ok = False
                if i<n-1 and a[i+1][j]==1: ok = False
                safe[i][j] = 1 if ok else 0

    maxk_seg = min(m, maxk)
    cnt = [0] * (maxk_seg+1)

    # 统计每种 k 的安全连续段
    for i in range(n):
        pref = [0]*(m+1)
        for j in range(m):
            pref[j+1] = pref[j] + safe[i][j]
        for k in range(1, maxk_seg+1):
            tot = 0
            for j in range(m-k+1):
                if pref[j+k] - pref[j] == k:
                    if j>0 and a[i][j-1]==1: continue
                    if j+k<m and a[i][j+k]==1: continue
                    tot += 1
            cnt[k] += tot

    # 输出结果
    res = []
    for k in qs:
        if k<=maxk_seg:
            res.append(str(cnt[k] * fac[k] % MOD))
        else:
            res.append('0')
    print(' '.join(res))

if __name__ == '__main__':
    main()

Java 代码

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 998244353;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        int[][] a = new int[n][m];
        // 读入座位矩阵
        for (int i = 0; i < n; i++) {
            String line = br.readLine().trim();
            String[] parts = line.split("\\s+");
            if (parts.length == m) {
                for (int j = 0; j < m; j++) a[i][j] = Integer.parseInt(parts[j]);
            } else {
                for (int j = 0; j < m; j++) a[i][j] = line.charAt(j) - '0';
            }
        }

        // 查询列表
        int[] qs = Arrays.stream(br.readLine().split("\\s+"))
                         .mapToInt(Integer::parseInt).toArray();
        int maxk = Arrays.stream(qs).max().orElse(0);

        // 阶乘
        long[] fac = new long[maxk+1]; fac[0]=1;
        for (int i = 1; i <= maxk; i++) fac[i] = fac[i-1]*i%MOD;

        // safe 数组
        int[][] safe = new int[n][m];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (a[i][j]==0) {
                boolean ok = true;
                if (i>0 && a[i-1][j]==1) ok = false;
                if (i<n-1 && a[i+1][j]==1) ok = false;
                safe[i][j] = ok ? 1 : 0;
            }
        }

        int maxkSeg = Math.min(m, maxk);
        long[] cnt = new long[maxkSeg+1];

        // 统计
        for (int i = 0; i < n; i++) {
            int[] pref = new int[m+1];
            for (int j = 0; j < m; j++) pref[j+1] = pref[j] + safe[i][j];
            for (int k = 1; k <= maxkSeg; k++) {
                int tot = 0;
                for (int j = 0; j+k <= m; j++) {
                    if (pref[j+k]-pref[j] == k) {
                        if (j>0 && a[i][j-1]==1) continue;
                        if (j+k<m && a[i][j+k]==1) continue;
                        tot++;
                    }
                }
                cnt[k] += tot;
            }
        }

        // 输出
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            int k = qs[i];
            long ans = (k>=1 && k<=maxkSeg) ? cnt[k]%MOD*fac[k]%MOD : 0;
            sb.append(ans).append(i<q-1?' ':'\n');
        }
        System.out.print(sb);
    }
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> a(n, vector<int>(m));
    string s;
    // 读入座位
    for (int i = 0; i < n; i++) {
        cin >> s;
        if ((int)s.size() == m && (s.find(' ') == string::npos)) {
            for (int j = 0; j < m; j++) a[i][j] = s[j] - '0';
        } else {
            // 不带空格时自动处理
            for (int j = 0; j < m; j++) a[i][j] = s[j] - '0';
        }
    }
    vector<int> qs(q);
    for (int i = 0; i < q; i++) cin >> qs[i];

    int maxk = *max_element(qs.begin(), qs.end());
    vector<ll> fac(maxk+1, 1);
    for (int i = 1; i <= maxk; i++) fac[i] = fac[i-1] * i % MOD;

    // safe 数组
    vector<vector<int>> safe(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        if (a[i][j]==0) {
            bool ok = true;
            if (i>0 && a[i-1][j]==1) ok = false;
            if (i<n-1 && a[i+1][j]==1) ok = false;
            safe[i][j] = ok;
        }
    }

    int maxkSeg = min(m, maxk);
    vector<ll> cnt(maxkSeg+1, 0);

    // 统计区间
    for (int i = 0; i < n; i++) {
        vector<int> pref(m+1, 0);
        for (int j = 0; j < m; j++) pref[j+1] = pref[j] + safe[i][j];
        for (int k = 1; k <= maxkSeg; k++) {
            int tot = 0;
            for (int j = 0; j+k <= m; j++) {
                if (pref[j+k] - pref[j] == k) {
                    if (j>0 && a[i][j-1]==1) continue;
                    if (j+k<m && a[i][j+k]==1) continue;
                    tot++;
                }
            }
            cnt[k] += tot;
        }
    }

    // 输出答案
    for (int i = 0; i < q; i++) {
        int k = qs[i];
        ll ans = 0;
        if (k>=1 && k<=maxkSeg) ans = cnt[k] % MOD * fac[k] % MOD;
        cout << ans << (i+1<q ? ' ' : '\n');
    }
    return 0;
}

题目内容

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

只能选择空闲座位；

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

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

现在，给出电影院的座位示意图，以及多次询问，每次询问给出 $k$ 个整教，表示你们希望一起观影的人数，请计算对于每次询问，有多少种不同的选座方案满足上述要求。两个方案不同当且仅当至少有一个人与之前的位置不同。若不存在任何合法方案，输出 $0$ 。由于答案可能很大，请将答案对 $998$ $244$ $353$ 取模后输出。

输入描述

第一行输入三个整数 $n,m,q(1≦n,m,q≦ 100)$ ，表示电影院座位的行数、列数、询问次数。

此后 $n$ 行，第 $i$ 行输入 $m$ 个整数 $a_{i,1},a_{i,2},...,a_{i,m}(0≦a_{i,j}≦1)$，其中 $a_{i,j}$ ，表示电影院第 $i$ 行第 $j$ 列的座位状态。$a_{i,j}=0$ 表示空用，$a_{i,j}=1$ 表示已被购买。

第 $n+2$ 行输入 $q$ 个整数 $k_1,k_2,...,k_q(1≦k_i≦n×m)$，表示每次询问中，你们希望一起观影的人数。

输出描述

对于每次询问，在一行上连续的输出一个整数，表示不同的选座方案数，由于答案可能很大，请将答案对 $998$ $244$ $353$ 取模后输出。

样例1

输入

1 3 4
0 0 0
0 1 2 3

输出

0 3 4 6

说明

对于第三次询问，有以下几种选座方案：

选择第 $1$ 行，第一个朋友坐第 $1$ 列，第二个朋友坐第 $2$ 列；

选择第 $1$ 行，第一个朋友坐第 $2$ 列，第二个朋友坐第 $1$ 列；

选择第 $1$ 行，第一个朋友坐第 $2$ 列，第二个朋友坐第 $3$ 列；

选择第 $1$ 行，第一个朋友坐第 $3$ 列，第二个朋友坐第 $2$ 列。

样例2

输入

2 4 3
1 1 0 1
0 0 0 0
1 3 8

输出

1 0 0

样例3

输入

4 4 2
1 0 0 0
0 0 0 0
0 0 0 1
1 1 0 1
1 2

输出

4 4