题目描述

难度分:$2600$

输入$h$、$w(1 \leq h,w \leq 3600)$和$n(0 \leq n \leq 2400)$。

有一个$h$行$w$列的棋盘，上面已经放了$n$个骨牌。一个骨牌由两个$1 \times 2$大小的相邻方块组成。

然后输入$n$行，每行$4$个数，表示每个骨牌的第一个方块的行号和列号，以及第二个方块的行号和列号。

行列编号从$1$开始。

定义完美平衡棋盘：对于每一行和每一列，要么没有方块，要么有一个方块，要么有两个方块且这两个方块属于同一个骨牌。保证输入的棋盘是完美平衡棋盘。

你需要继续往棋盘上放零块或更多的骨牌，使得棋盘仍然是完美平衡的。输出方案数，模$998244353$。

输入样例$1$

5 7 2
3 1 3 2
4 4 4 5

输出样例$1$

8

输入样例$2$

5 4 2
1 2 2 2
4 3 4 4

输出样例$2$

1

输入样例$3$

23 42 0

输出样例$3$

102848351

算法

真难，做不了一点！

计数DP

先决定横着的骨牌放哪些相邻的列，竖的骨牌放哪些相邻的行。把这些位置剔除掉之后又按这个套路，决定横的骨牌放哪些列，竖的骨牌放哪些行。用$visx$和$visy$两个布尔数组来标记，$visx[i]=$true表示第$i$行有骨牌，$visy[j]=$true表示第$j$列有骨牌。$restx$和$resty$表示摆放完已有的$n$个骨牌之后，还剩下的行数和列数。

状态定义

$f[i][j]$表示前$i$行选$j$个相邻行放骨牌的方案数，$g[i][j]$表示前$i$列选$j$和相邻列放骨牌的方案数。

状态转移

以$f$的状态转移来进行说明，在第$i$行有两种选择：

1. 第$i$行不放骨牌，那么相邻的$j$行就是之前$i-1$行放出来的，即$f[i-1][j]$。
2. 否则放一个竖着的骨牌，就有$j-1$个相邻行是前$i-2$行放出来的，把$f[i-2][j-1]$累加到$f[i][j]$上。

$g[i][j]$也是类似分析，但是放横着的骨牌。综上，最终的答案就是

$\Sigma_{i=0}^{\lfloor \frac{restx}{2} \rfloor}\Sigma_{j=0}^{\lfloor \frac{resty}{2} \rfloor}f[h][i] \times g[w][j] \times C(resty-2j,i) \times C(restx-2i,j) \times i! \times j!$

其中$C(n,m)$表示组合数，从$n$个中选择$m$个出来。减去两倍的$i$和$j$是因为放一个横放的骨牌相当于占掉一行两列，放一个竖放的骨牌相当于占掉一列两行。

复杂度分析

时间复杂度

求$f$的DP值时间复杂度为$O(h^2)$；求$g$的DP值时间复杂度为$O(w^2)$；最后求总答案需要遍历矩阵，时间复杂度为$O(hw)$。因此，整个算法的时间复杂度为$O(h^2+w^2+hw)$。

空间复杂度

空间消耗主要在于$f$和$g$两个DP矩阵，空间复杂度为$O(h^2+w^2)$。求组合数时需要求逆元，但是空间是线性的。因此，整个算法的额外空间复杂度为$O(h^2+w^2)$。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3605;
const int MOD = 998244353;
int h, w, n;
bool visx[N], visy[N];
LL f[N][N], g[N][N], inv[N], finv[N], fi[N];

// 预处理逆元
void get_inv(int n) {
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++) {
        inv[i] = (MOD - MOD/i) * inv[MOD % i] % MOD;
    }
    finv[0] = finv[1] = fi[0] = fi[1] = 1;
    for(int i = 2; i <= n; i++) {
        fi[i] = fi[i - 1] * i % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 排列数
LL A(LL n, LL m) {
    if(n < m) return 0;
    return fi[n] * finv[n - m] % MOD;
}

int main() {
    get_inv(N - 5);
    scanf("%d%d%d", &h, &w, &n);
    int restx = 0, resty = 0;
    for(int i = 1; i <= n; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        visx[a] = visx[c] = visy[b] = visy[d] = true;
    }
    for(int i = 1; i <= h; i++) {
        restx += 1 - visx[i];
    }
    for(int i = 1; i <= w; i++) {
        resty += 1 - visy[i];
    }
    f[0][0] = g[0][0] = 1;
    for(int i = 1; i <= h; i++) {
        for(int j = 0; j*2 <= restx; j++) {
            f[i][j] = (f[i - 1][j] + ((j && i >= 2 && !visx[i] && !visx[i - 1])? f[i - 2][j - 1]: 0)) % MOD;
        }
    }
    for(int i = 1; i <= w; i++) {
        for(int j = 0; j*2 <= resty; j++) {
            g[i][j] = (g[i - 1][j] + ((j && i >= 2 && !visy[i] && !visy[i - 1])? g[i - 2][j - 1]: 0)) % MOD;
        }
    }
    LL ans = 0;
    for(int i = 0; i*2 <= restx; i++) {
        for(int j = 0; j*2 <= resty; j++) {
            ans = (ans + f[h][i] * g[w][j] % MOD * A(restx - 2*i, j) % MOD * A(resty - 2*j, i)) % MOD;
        }
    }
    printf("%lld\n", ans);
    return 0;
}