LOJ #3409. 「2020-2021 集训队作业」Yet Another Linear Algebra Problem 题解

Description

您需要解决两个独立（但类似）的子问题：

问题一：给定 $n$ 个在 $\mathrm{GF}(3)$ 上的 $m$ 维向量，记它们张成的线性空间为 $V$。求从 $n$ 个向量中选出一组向量，使得它们是 $V$ 的基的方案数。对 $3$ 取模。

问题二：给定 $n$ 个在 $\mathrm{GF}(2)$ 上的 $m$ 维向量，记它们张成的线性空间为 $V$。其中第 $i$ 个向量有颜色 $c_i$。求从每种颜色中恰好选出一个向量，使得它们是 $V$ 的基的方案数。对 $2$ 取模。

注：为了凸显主要矛盾而忽略次要矛盾，保证 $V$ 的维数为 $m$。

$1\leq n,m\leq 500$。

Solution

首先有个前置知识是 Binet Cauchy 公式：

对于 $m\times n$ 的矩阵 $A$ 和 $n\times m$ 的矩阵 $B$（$n\geq m$），有：（$A_S,B_S$ 表示列/行下标在 $S$ 中的子矩阵）

$$\det(AB)=\sum_{|S|=m}{\det(A_S)\det(B_S)}$$

第一问就是问有多少个大小为 $m$ 的子集，使得这个子集的秩非零。注意到在模 $3$ 意义下，$[x\neq 0]=x^2$，所以问题变为 $\displaystyle\sum_{|S|=m}{\det(A_S)^2}=\det(A^TA)$。

第二问等价于问 $\displaystyle\sum_{|S|=m}{\det(A_S)[\cup_{i\in S}{\{c_i\}}=U]}$，其中 $u$ 是颜色全集。考虑将第二个条件转为一个 $n\times m$ 的矩阵的行列式。

容易发现这等价于让 $B_{i,j}=[j=c_i]$，如果 $S$ 中有元素颜色相同，则 $B_S$ 的秩一定是 $0$，否则是 $1$。于是答案为 $\det(A^TB)$。

时间复杂度：$O(n^3)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 505;

int taskid, n, m, mod;

struct Matrix {
  int n, m, a[kMaxN][kMaxN];
  void set(int _n, int _m) { n = _n, m = _m; }
  friend Matrix operator *(Matrix &a, Matrix &b) {
    static Matrix ret;
    assert(a.m == b.n);
    ret.set(a.n, b.m);
    for (int i = 1; i <= a.n; ++i) {
      for (int j = 1; j <= b.m; ++j) {
        ret.a[i][j] = 0;
        for (int k = 1; k <= a.m; ++k) ret.a[i][j] += a.a[i][k] * b.a[k][j];
        ret.a[i][j] %= mod;
      }
    }
    return ret;
  }
} a, b;

int getdet(Matrix a) {
  assert(a.n == a.m);
  int n = a.n, ret = 1;
  for (int i = 1; i <= n; ++i) {
    if (!a.a[i][i]) {
      for (int j = i + 1; j <= n; ++j) {
        if (a.a[j][i]) {
          std::swap(a.a[i], a.a[j]), ret = mod - ret;
          break;
        }
      }
    }
    if (!a.a[i][i]) return 0;
    ret = ret * a.a[i][i] % mod;
    for (int j = i + 1; j <= n; ++j) {
      int d = a.a[j][i] * a.a[i][i];
      for (int k = i; k <= n; ++k) a.a[j][k] = (a.a[j][k] - a.a[i][k] * d + 3 * mod) % mod;
    }
  }
  return (ret % mod + mod) % mod;
}

void dickdreamer() {
  std::cin >> taskid >> n >> m;
  if (taskid == 1) {
    mod = 3, a.set(m, n), b.set(n, m);
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j)
        std::cin >> b.a[i][j], a.a[j][i] = b.a[i][j];
    std::cout << getdet(a * b) << '\n';
  } else {
    mod = 2, a.set(m, n), b.set(n, m);
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j)
        std::cin >> a.a[j][i];
      int c;
      std::cin >> c;
      b.a[i][c] = 1;
    }
    std::cout << getdet(a * b) << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}