Mild_Donkey

线性代数4 行列式

Determinant

对于一个 $n$ 阶方阵 (行列相等的矩阵) $A$ , 定义 $\det(A)$ 表示它的行列式 (Determinant). 如果认为 $S_n$ 是 $[1, n]$ 中正整数的所有 $n!$ 种置换的集合. $\mathrm{sgn}(\sigma)$ 在 $\sigma$ 为奇排列时为 $-1$ , 是偶排列时是 $1$ , 那么方阵 $A$ 的行列式可以表示为:

\det(A) = \sum_{\sigma \in S_n} \mathrm{sgn}(\sigma) \prod_{i = 1}^n A_{i, \sigma(i)}

如果直接求那复杂度将是 $O(n!n)$ 的, 我们仍然使用高斯消元. 其原理是:

任意两行(列)交换, 结果取反
某行(列)加减另一行(列), 结果不变
某行(列)乘以 $k$ 倍, 结果乘以 $k$

我们用前面的变换将矩阵只留下第 $i$ 行后 $i$ 项的过程中记一下结果会变成之前的多少倍即可.

然后是求行列式, 发现所有第 $i$ 项不是 $i$ 的置换都不需要枚举了, 因为它的 $\prod$ 中一定有至少一项是 $0$ , 对结果没有贡献. 我们只要对这个矩阵对角线上的元素求积即可.

当需要取模时, 模数任意的情况下我们可能无法找到所需的逆元, 所以我们采用辗转相减法进行消元. 两行之间的减法是 $O(n)$ 的, 每次消掉一个位置的元素需要 $O(\log p)$ 次减法. 一共需要消 $O(n^2)$ 个元素, 所以复杂度是 $O(n^3\log p)$ . 但是因为我们是连续消掉一列的元素, 每次相减后, 对应位置剩下的元素是上面所有元素的 GCD, 所以消掉一列元素均摊需要 $O(n + \log p)$ 次减法, 因此更精确的复杂度应该是 $O(n^2(n + \log p))$ .

下面是模板题代码:

unsigned long long Gcd(unsigned long long x, unsigned long long y) {
  unsigned long long SwT;
  while (y) SwT = x, x = y, y = SwT % y;
  return x;
}
unsigned long long a[605][605], Mod, G, Tms(1), Ans(1);
unsigned m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0);
inline void Dec(unsigned long long* f, unsigned long long* g, unsigned x) {
  while (g[x]) {
    unsigned long long Tmp(Mod - (f[x] / g[x]));
    for (unsigned i(x); i <= n; ++i) f[i] = (f[i] + g[i] * Tmp) % Mod;
    for (unsigned i(x); i <= n; ++i) swap(f[i], g[i]);
    Tms = Mod - Tms;
  }
}
signed main() {
  n = RD(), Mod = RD();
  for (unsigned i(1); i <= n; ++i) for (unsigned j(1); j <= n; ++j) a[i][j] = RD() % Mod;
  if (n == 1) { printf("%llu\n", a[1][1]);return 0; }
  for (unsigned i(1); i <= n; ++i) {
    G = Gcd(a[i][1], a[i][2]);
    for (unsigned j(3); j <= n; ++j) G = Gcd(G, a[i][j]);
    if (G > 1) for (unsigned j(1); j <= n; ++j) a[i][j] /= G;
    Tms = Tms * G % Mod;
  }
  for (unsigned i(1); i <= n; ++i) {
    G = Gcd(a[1][i], a[2][i]);
    for (unsigned j(3); j <= n; ++j) G = Gcd(G, a[j][i]);
    if (G > 1) for (unsigned j(1); j <= n; ++j) a[j][i] /= G;
    Tms = Tms * G % Mod;
  }
  for (unsigned i(1); i <= n; ++i) for (unsigned j(n); j > i; --j) if (a[j][i]) Dec(a[j - 1], a[j], i);
  for (unsigned i(1); i <= n; ++i) Ans = Ans * a[i][i] % Mod;
  printf("%llu\n", Ans * Tms % Mod);
  return Wild_Donkey;
}