蓝桥杯国赛 矩阵计数（python-状压DP）

矩阵计数是一道经典的组合数学问题，可以用状压DP来解决。以下是一份Python代码的参考实现。

首先，我们需要输入矩阵的行数和列数，以及每行和每列的限制数。然后，我们可以使用二进制数来表示每行和每列的状态，其中1表示该行或该列已经有了一个矩阵，0表示该行或该列还可以放置一个矩阵。

接下来，我们可以使用状压DP来计算矩阵的数量。我们可以定义一个三维数组dp，其中dp[i][j][s]表示在第i行，第j列，状态为s时的矩阵数量。可以通过枚举上一个状态s'，来更新dp[i][j][s]。具体来说，如果s'与s在第i行和第j列上的状态都是0，则可以从dp[i][j-1][s']或dp[i-1][j][s']转移而来。如果s'与s在第i行或第j列上的状态不同，则不能转移。最后，dp[m][n][0]就是最终的答案。

下面是完整的代码实现：

n, m, k1, k2 = map(int, input().split())

# 行状态用二进制数表示
row_mask = [0] * n
for i in range(n):
    row_mask[i] = int(''.join(input().split()), 2)

# 列状态用二进制数表示
col_mask = [0] * m
for j in range(m):
    col_mask[j] = int(''.join(input().split()), 2)

# 初始化dp数组
dp = [[[0 for _ in range(1 << m)] for _ in range(m + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

# 状压DP
for i in range(1, n + 1):
    for j in range(m + 1):
        for s in range(1 << m):
            for sp in range(1 << m):
                # 如果s'与s在第i行和第j列上的状态都是0，则可以从dp[i][j-1][s']或dp[i-1][j][s']转移而来
                if (sp & s) == 0 and (row_mask[i - 1] & sp) == 0 and (col_mask[j - 1] & sp) == 0:
                    if j == 0:
                        dp[i][1][sp] += dp[i - 1][m][s]
                    else:
                        dp[i][j + 1][sp] += dp[i][j][s] + dp[i - 1][j][s]
                # 如果s'与s在第i行或第j列上的状态不同，则不能转移
                else:
                    continue

# 计算答案
ans = 0
for s in range(1 << m):
    if bin(s).count('1') == k2:
        ans += dp[n][m][s]

print(ans % 998244353)

其中，我们使用了Python内置的bin函数来将一个整数转换为二进制字符串，并使用count方法来计算其中1的个数。