题目分析

题目定义了两个 $N \times N$ 的 0-1 矩阵 $A$ 和 $B$ 的乘法运算：

$$C_{i,j} = \left(\sum_{k=1}^N A_{i,k} B_{k,j}\right) \bmod 2 $$

现在给定矩阵 $C$，要求计算有多少个有序对 $(A,B)$ 满足 $A \times B \equiv C \pmod{2}$。

关键思路

1. 模2运算的线性代数性质

在模2运算下，矩阵乘法具有线性性质。我们可以将问题重新表述：

对于固定的 $A$，方程 $A \times B = C$ 在模2意义下是一个线性方程组。具体来说，对于 $B$ 的每一列 $j$，我们有：

$$A \cdot B_{:,j} = C_{:,j}$$

其中 $B_{:,j}$ 和 $C_{:,j}$ 分别表示 $B$ 和 $C$ 的第 $j$ 列。

2. 解的个数分析

对于线性方程组 $A \cdot x = b$ 在模2意义下：

• 如果方程组有解，解的个数为 $2^{N - \text{rank}(A)}$，其中 $\text{rank}(A)$ 是矩阵 $A$ 在模2意义下的秩
• 如果方程组无解，解的个数为 0

因此，对于固定的 $A$，满足 $A \times B = C$ 的矩阵 $B$ 的数量为：

• 如果对于所有列 $j$，方程组 $A \cdot B_{:,j} = C_{:,j}$ 都有解，则 $B$ 的数量为 $2^{N(N - \text{rank}(A))}$
• 否则为 0

3. 对所有 $A$ 求和

我们需要计算所有可能的 $A$ 对应的 $B$ 的数量之和：

$$\text{答案} = \sum_{A} [A \times B = C \text{ 有解}] \cdot 2^{N(N - \text{rank}(A))} $$

关键观察：$A \times B = C$ 对所有列都有解当且仅当 $C$ 的列空间包含在 $A$ 的列空间中，即 $\text{rank}([A|C]) = \text{rank}(A)$。

4. 最终公式

通过线性代数推导（涉及商空间维数），可以得到最终答案：

设 $r = \text{rank}(C)$，则答案为：

$$\text{答案} = 2^{N(N - r)} \cdot \prod_{k=0}^{r-1} (2^N - 2^k)^2 \cdot 2^{-r(N-r)} $$

简化后：

$$\text{答案} = \prod_{k=0}^{r-1} (2^{N-k} - 1)^2 \cdot 2^{N(N-r)} $$

算法步骤

1. 使用高斯消元法计算矩阵 $C$ 在模2意义下的秩 $r$
2. 根据公式计算答案：$$\text{答案} = \prod_{k=0}^{r-1} (2^{N-k} - 1)^2 \cdot 2^{N(N-r)} \mod (10^9+7) $$
3. 输出答案

代码实现（C++）

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

const int MOD = 1e9 + 7;

// 高斯消元求矩阵的秩（模2）
int matrixRank(vector<vector<int>>& matrix, int n) {
    int rank = 0;
    vector<bool> row_used(n, false);
    
    for (int col = 0; col < n; col++) {
        int pivot = -1;
        // 寻找主元
        for (int row = 0; row < n; row++) {
            if (!row_used[row] && matrix[row][col] == 1) {
                pivot = row;
                break;
            }
        }
        
        if (pivot == -1) continue;
        
        rank++;
        row_used[pivot] = true;
        
        // 消去其他行
        for (int row = 0; row < n; row++) {
            if (!row_used[row] && matrix[row][col] == 1) {
                for (int c = col; c < n; c++) {
                    matrix[row][c] ^= matrix[pivot][c];
                }
            }
        }
    }
    
    return rank;
}

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> C(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> C[i][j];
        }
    }
    
    // 计算矩阵C的秩
    int r = matrixRank(C, n);
    
    // 预计算2的幂次
    vector<long long> pow2(n * n + 1);
    pow2[0] = 1;
    for (int i = 1; i <= n * n; i++) {
        pow2[i] = (pow2[i-1] * 2) % MOD;
    }
    
    // 计算答案
    long long ans = pow2[n * (n - r)];  // 2^(N(N-r))
    for (int k = 0; k < r; k++) {
        long long term = (pow2[n - k] - 1 + MOD) % MOD;
        ans = (ans * term % MOD * term) % MOD;
    }
    
    cout << ans << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(N^3)$，主要来自高斯消元
• 空间复杂度：$O(N^2)$，用于存储矩阵

对于 $N \leq 2000$ 的数据范围，$O(N^3)$ 的算法可能无法通过。实际比赛中需要使用更高效的高斯消元实现或利用位运算优化。

总结

本题的关键是将矩阵计数问题转化为线性代数问题，通过分析矩阵的秩来得到简洁的计数公式。这种将组合计数问题与线性代数结合的思想在竞赛中很常见。