【11.25】【VP】 45 届 济南站

ALL：13
AC：4
补题：1
Rank：196

D 题 wa 了两发，每一发都要掉十几名几十名，有点哈人（

---

Matrix Equation

题意：

定义 01 正方矩阵的叉乘和点乘。现在给你宽为 $n(1\le n\le 200)$ 的 01 正方矩阵 $A,B$ ，问你有多少种同等大小的矩阵 $C$ 满足 $A\times C=B\odot C$ 。方案数对 $998244353$ 取模。

思路：VP 时打了两个小时的表，最佳结果是只过了样例。

考虑固定 $j\in [1,n]$ ，这样我们有 $n$ 个 01 变量 $C_{i,j}$ 。我们枚举 $i\in [1,n]$ ，可以构建出 $n$ 个包含 $C_{i,j}$ 的多元方程，形式如：

$$\sum _{k=1}^n(A_{i,k}\cdot C_{k,j})\%2=B_{i,j}\cdot C_{i,j}$$

构建出 $n$ 个方程之后，高斯消元，得到自由元的数量 $c_j$ ，累加起来为 $c=\sum c_j$ ，答案即为 $2^c$ 。

该朴素思路时间复杂度为 $O(n^4)$ ，但是能跑 706 ms ，估计是跑不满 $n^4$ 。

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=54997315