选位置

题目

上课的时候你该不会想和老师挨着坐吧。

新学期，小J和小R一起来到了要上课的教室，不过他们仔细一看，发现黎叔也坐在了教室里面，所有同学选择位置的时候都默契的避开了黎叔周围的八个位置。

小R："你说如果包含黎叔每一列都只能坐一个人，同学们都不在黎叔周围，并且没有人左右相邻的话一共能有多少种坐法呀。"

小J："不是……怎么什么问题都能问我。"

小R："不知道就是不知道，不必解释。"

为了挽回尊严，小J又需要你的帮助。

教室里有 n 行 m 列个座位，其中黎叔已经坐在了一个位置上，请你告诉小J：包含黎叔在内，每一列都只能坐一个人，且没有同学在黎叔周围的坐法一共有多少种。

输入：第一行两个整数 n, m，n 表示座位行数，m 表示座位列数。第二行两个整数 x, y，表示黎叔在 x 行 y 列。
输出：一个整数，表示符合要求的方案数。（由于数据可能较大，答案请取模 998244353 输出）

样例1：

3 3
1 1

2

样例2：

5 5
3 3

64

思路

按列从左到右做 DP：dp[r] 表示当前列选第 r 行时，前面所有列的合法方案数之和。 转移公式为 ndp[r] = S - dp[r]，其中 S 为上一列所有合法行的方案总和，减去 dp[r] 是为了排除相邻列同行的情况。 特殊处理三列：第 y 列只有第 x 行合法（黎叔固定位置）；第 y-1 和 y+1 列的第 x-1、x、x+1 行禁止落座（黎叔周围八格）；其余列所有行均合法。 不合法的行直接跳过，最终答案为最后一列所有 dp[r] 之和。

#include<bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,x,y;
    cin>>n>>m>>x>>y;
    x--; y--;

    // dp[r] = 当前列选第r行时，前面所有列的方案数之和
    vector<long long> dp(n, 0);

    // 判断第j列第r行是否合法
    auto ok = [&](int j, int r) -> bool {
        if (j == y) return r == x;
        if (j == y-1 || j == y+1)
            return r < x-1 || r > x+1;
        return true;
    };

    // 初始化第0列
    for (int r = 0; r < n; r++)
        if (ok(0,r)) dp[r] = 1;

    for (int c = 1; c < m; c++){
        long long S = 0;
        for (int r = 0; r < n; r++) S = (S + dp[r]) % MOD;
        vector<long long> ndp(n, 0);
        for (int r = 0; r < n; r++)
            if (ok(c,r)) ndp[r] = (S - dp[r] + MOD) % MOD;
        dp = ndp;
    }

    long long ans = 0;
    for (int r = 0; r < n; r++) ans = (ans + dp[r]) % MOD;
    cout << ans << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：O(nm)，逐列推进，每列 O(n)。
• 空间复杂度：O(n)，只保留当前列的 dp 数组。

← 返回菜鸟的coding