首页 > 其他分享 >P7112 题解

P7112 题解

时间：2023-07-08 19:13:48浏览次数：70  
标签：P7112 tau ddots 题解 vmatrix times cdots vdots

题意简述

模板题，求一个 \(n\times n(n\le 600)\) 的方阵的行列式模一个正整数 \(p(1\le p\le 10^9+7)\) 的值（\(p\) 不一定是质数）。

题目分析

这个题的最终代码其实很简单，重点在于过程。说实话，我在做这个题之前也就只知道个行列式的定义，只会暴力硬算。做了这个题才了解了行列式有那么多的好的性质，也算是开了开眼界吧。所以本文先介绍行列式本身再讲解题步骤。由于这篇文章本身也是我在学习 @Reywmp 大佬的 数学(5)——线性代数：行列式 一文之后写的，所以本文参考了这篇文章的内容，在此先膜拜大佬。另外我个人十分重视性质的证明过程，所以把自己写的几个性质的证明直接放到了文中，读者可以选择性看一看。（最好看看吧，毕竟我肝了将近两个小时）

定义

首先来看行列式的定义。对于一个 \(n\times n\) 的矩阵 \(A\)：

\[A= \begin{bmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{k,1}& a_{k,2}& \cdots & a_{k,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{bmatrix} \]

它的行列式就是：

\[|A|=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k} \]

其中 \(p\) 是 \(\{1,2,3,\cdots,n-1,n\}\) 的排列，\(\tau(p)\) 则是 \(p\) 中的逆序对个数。

形象化一点，你可以认为 \(\prod_{k=1}^n a_{k,p_k}\) 是由 \(p\) 决定的矩阵中两两不同行不同列的 \(n\) 个元素的乘积。如果 \(p\) 的逆序对个数为偶数，就把这个乘积加到总和里；反之，就从总和里把这个乘积减去。这样得到的总和就是矩阵的行列式。

那么这个看起来有点抽象的东西有什么实际用途呢？一个经典的例子是这样的：\(n\times n\) 的矩阵本身对应着 \(n\) 维欧式空间中的一个线性变换，而这个矩阵的行列式就对应着这个线性变换前后的“体积”之比。由于这部分不是特别重要，本文不过多展开。感兴趣的读者可以自行查询资料，如行列式的意义是什么？——知乎。

性质

行列式的性质有很多，在这里只介绍较为有用的几个。

1. 交换矩阵的两行或两列，行列式取反。

证明：交换矩阵的第 \(i\) 行与第 \(j\) 行，对行列式产生的实际影响是将原先的每一个 \(\prod_{k=1}^n a_{k,p_k}\) 中，原来的 \(a_{i,p_i}\) 换到了第 \(j\) 行，而原来的 \(a_{j,p_j}\) 换到了第 \(i\) 行，对应的也就是将每个排列 \(p\) 中的 \(p_i\) 与 \(p_j\) 两项交换。这一交换的作用则是改变了 \(\tau(p)\)，也就是说，我们只需要证明交换后的排列 \(p'\) 满足 \(\tau(p')\) 与 \(\tau(p)\) 奇偶性不同即可。

不妨设 \(i<j\)。交换 \(p_i\) 与 \(p_j\) 使 \(\tau(p)\) 产生的变化来自于：

1.\(p_i\) 与 \(p_j\) 大小关系必然变化（这是因为 \(p\) 是 \(\{1,2,3,\cdots,n\}\) 的排列，所以 \(p_i ≠ p_j\)），\(\tau(p)\) 加 1 或减 1。

2.\(p_i\) 与 \(p_k\)（\(\forall k\in(i,j)\)）的大小关系发生的变化，设满足 \(p_i<p_k\) 的 \(k\) 有 \(a\) 个，则 \(p_k<p_i\) 的 \(k\) 有 \(j-i+1-a\) 个，\(\tau(p)\) 增加或减少 \(|j-i+1-2a|\)。

3.\(p_j\) 与 \(p_k\)（\(\forall k\in(i,j)\)）的大小关系发生的变化，设满足 \(p_j<p_k\) 的 \(k\) 有 \(b\) 个，则 \(p_k<p_j\) 的 \(k\) 有 \(j-i+1-b\) 个，\(\tau(p)\) 增加或减少 \(|j-i+1-2b|\)。

注意到 \(|j-i+1-2a|\) 和 \(|j-i+1-2b|\) 与 \(j-i+1\) 奇偶性均相同，那么就有 \(|j-i+1-2a|\pm|j-i+1-2b|\) 必定为偶数。也就是说，上文的第 2、3 类大小关系的改变不会使 \(\tau(p)\) 的奇偶性产生改变，因此能够使得 \(\tau(p)\) 奇偶性改变的只有第 1 类改变。这就表明 \(\tau(p)\) 的奇偶性必将发生变化。

交换列的情况类似。

2. 如果矩阵的某两行（列）相同，行列式为 0。

证明：交换矩阵相同的两行（列），矩阵不变，那么行列式也不变。但是由性质 1 得到前后的行列式是相反数，这就推出行列式为 0。

3. 矩阵的某一行（列）的每个元素乘（除） \(m\)，行列式也乘（除） \(m\)。

证明：设矩阵的第 \(i\) 行乘了 \(m\)，那么 \(|A|=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k}\) 中的每一个 \(a_{i,p_i}\) 都乘上了 \(m\)。所以 \(|A|\) 也乘上了 \(m\)。

推论：由性质 2 和 3 可得到：若矩阵中有两行（列）的所有元素成比例，则其行列式为 0。

4. 若矩阵 \(A\) 中有一行（列）的每个元素都是 2 个矩阵 B 与 C 中对应的元素之和，其它行（列）的所有元素与 \(B\)、\(C\) 相同，则 \(|A|=|B|+|C|\)

证明：设为第 \(i\) 行，则 \(\forall j\in[1,n]\)，有 \(a_{i,j}=b_{i,j}+c_{i,j}\)，且 \(\forall x,y\in[1,n],x≠i\)，有 \(a_{x,y}=b_{x,y}=c_{x,y}\)

那么有：

\(\ \ \ \ \displaystyle|B|+|C|\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n b_{k,p_k}+\sum_p (-1)^{\tau(p)}\prod_{k=1}^n c_{k,p_k}\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} b_{k,p_k})\times(b_{i,p_i})\times(\prod_{k=i+1}^n b_{k,p_k})]+\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} c_{k,p_k})\times(c_{i,p_i})\times(\prod_{k=i+1}^n c_{k,p_k})]\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} a_{k,p_k})\times(b_{i,p_i})\times(\prod_{k=i+1}^n a_{k,p_k})+(\prod_{k=1}^{i-1} a_{k,p_k})\times(c_{i,p_i})\times(\prod_{k=i+1}^n a_{k,p_k})]\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} a_{k,p_k})\times(b_{i,p_i}+c_{i,p_i})\times(\prod_{k=i+1}^n a_{k,p_k})]\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} a_{k,p_k})\times(a_{i,p_i})\times(\prod_{k=i+1}^n a_{k,p_k})]\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k}\)

\(\displaystyle=|A|\)

推论：若矩阵 \(A\) 中有一行（列）的每个元素都是 \(m\) 个矩阵 \(B_1,B_2,\cdots,B_n\) 中对应的元素之和，其它行（列）的所有元素与 \(B_1,B_2,\cdots,B_n\) 相同，则 \(|A|=|B_1|+|B_2|+\cdots+|B_n|\)。

5.把矩阵的某一行（列）乘上一个系数 \(m\)，加到另一行（列）上，矩阵行列式不变。

证明：设第 \(j\) 行乘上 \(m\) 后加到第 \(i\) 行上，也就是：

\[\begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i,1}+m\times a_{j,1}& a_{i,2}+m\times a_{j,2}& \cdots & a_{i,n}+m\times a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{j,1}& a_{j,2}& \cdots & a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix} \]

由性质 4 ，

\[\begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i,1}+m\times a_{j,1}& a_{i,2}+m\times a_{j,2}& \cdots & a_{i,n}+m\times a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{j,1}& a_{j,2}& \cdots & a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix} = \begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ m\times a_{j,1}& m\times a_{j,2}& \cdots & m\times a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{j,1}& a_{j,2}& \cdots & a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix} + \begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i,1}& a_{i,2}& \cdots & a_{i,n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{j,1}& a_{j,2}& \cdots & a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix} \]

由性质 2、3 的推论，

\[\begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ m\times a_{j,1}& m\times a_{j,2}& \cdots & m\times a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{j,1}& a_{j,2}& \cdots & a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix}=0 \]

则

\[\begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i,1}+m\times a_{j,1}& a_{i,2}+m\times a_{j,2}& \cdots & a_{i,n}+m\times a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{j,1}& a_{j,2}& \cdots & a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix} = \begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i,1}& a_{i,2}& \cdots & a_{i,n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{j,1}& a_{j,2}& \cdots & a_{j,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix} \]

证毕。

6. 矩阵的行列式等于其任意一行（列）的每个元素及其代数余子式的乘积之和

先解释下什么是代数余子式。我们称一个矩阵去掉第 \(i\) 行和第 \(j\) 列后剩下的矩阵的行列式为其余子式 \(M_{i,j}\)，而代数余子式 \(A_{i,j}=(-1)^{i+j}\times M_{i,j}\)。

那么原命题就是对于第 \(i\) 行，有 \(\displaystyle|A|=\sum_{j=1}^na_{i,j}\times A_{i,j}\)；

且对于第 \(j\) 列，有 \(\displaystyle|A|=\sum_{i=1}^na_{i,j}\times A_{i,j}\)。

证明：以第 \(i\) 行为例，由性质 4 的推论，得到：

\[\begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i,1}& a_{i,2}& \cdots & a_{i,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix} = \begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i,1}& 0& \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix}+\begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ 0& a_{i,2}& \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix}+\cdots + \begin{vmatrix} a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ 0& 0& \cdots & a_{i,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}& a_{n,2}& \cdots & a_{n,n} \end{vmatrix} \]

其中，有

\[\begin{vmatrix} a_{1,1}& a_{1,2}&\cdots&a_{1,j}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}&\cdots&a_{2,j}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots &\ddots&\vdots\\ 0& 0&\cdots&a_{i,j}& \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots &\ddots&\vdots\\ a_{n,1}& a_{n,2}&\cdots&a_{n,j}& \cdots & a_{n,n} \end{vmatrix}=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k} \]

显然，\(\displaystyle(-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k}\) 只有当 \(p_i=j\) 时才不为0，也就是说可以认为此时 \(p_i\) 固定为 \(j\) 。那么 \(p\) 现在不固定的实际上是 \(\{1,2,\cdots,j-1,j+1,\cdots,n\}\) 的排列，设为 \(p'\)。至于前面的 \((-1)^{\tau(p)}\)，我们可以把 \(\tau(p)\) 分解为与 \(i\) 有关的逆序对数量 \(m\) 和 \(\tau(p')\)。 注意到与 \(i\) 有关的逆序对数量就是满足以下两条件之一的整数 \(k\) 的数量：

  • \(k<i,p_k>j\)
  • \(k>i,p_k<j\)

若 \(i<j\)，考虑原始排列 \(p=\{1,2,3,\cdots,i-2,i-1,j,\cdots,n\}\)，此时满足 \(\forall k<i,p_k<j\)， \(m=(j-1)-(i-1)=j-i\)。若 \(i>j\)，考虑原始排列 \(p=\{1,\cdots,j,i+1,i+2,\cdots,n-2,n-1,n\}\)，此时满足 \(\forall k>i,p_k>j\)，则 \(m=(i-1)-(j-1)=i-j\)。而每次构造一个新的合法排列（即满足 \(p_i=j\) 的排列）时需要交换 \(i\) 之前的某数和 \(i\) 之后的某数，设分别为 \(p_{i_1}\) 和 \(p_{i_2}(i_1<i<i_2)\)，那么分以下几种情况：

  1. \(p_{i_1}<j\)，\(p_{i_2}<j\) 或 \(p_{i_1}>j\)，\(p_{i_2}>j\)

    ​ \(m\) 不变。

  2. \(p_{i_1}<j\)，\(p_{i_2}>j\)

    ​ \(m\) 增加 2。

  3. \(p_{i_1}>j\)，\(p_{i_2}<j\)

    ​ \(m\) 减少 2。

这就表明，每个合法排列的 \(k\) 的奇偶性与原始排列相同，也就是 \(m≡|i-j|≡i+j(\mod2)\)，所以 \((-1)^{\tau(p)}=(-1)^{{\tau(p')}+m}=(-1)^{\tau(p')}\times(-1)^m=(-1)^{\tau(p')}\times(-1)^{i+j}\)。

那么就有

\[\begin{vmatrix} a_{1,1}& a_{1,2}&\cdots&a_{1,j}& \cdots & a_{1,n} \\ a_{2,1}& a_{2,2}&\cdots&a_{2,j}& \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots &\ddots&\vdots\\ 0& 0&\cdots&a_{i,j}& \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots &\ddots&\vdots\\ a_{n,1}& a_{n,2}&\cdots&a_{n,j}& \cdots & a_{n,n} \end{vmatrix}=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k}= a_{i,j}\times(-1)^{i+j}\times\sum_{p'} (-1)^{\tau({p'})}\prod_{k=1}^n a_{k,{p'}_k}=a_{i,j}\times A_{i,j} \]

证毕。

解题步骤

本题直接暴力求值的时间复杂度为 \(O(n\times n!)\)，显然无法接受。

考虑之前的性质 1、3、5 中的操作，形式是不是有点熟悉？没错，它们就是矩阵的初等变换。而在高斯消元中，我们可以通过初等行变换进行消元将一个矩阵变为一个上三角矩阵。所以，我们只要能够求出消元后的上三角矩阵的行列式，就可以很简单地计算出原矩阵的行列式。

所以问题来了，怎么快速计算上三角矩阵的行列式？举个例子：

\[\begin{bmatrix} a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-1}& a_{1,n} \\ 0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-1}& a_{2,n} \\ 0& 0& a_{3,3}&\cdots &a_{3,n-1}& a_{3,n} \\ \vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\ 0& 0&0&\cdots &a_{n-1,n-1}& a_{n-1,n} \\ 0& 0&0&\cdots &0& a_{n,n} \end{bmatrix} \]

根据性质 6，有

\[\begin{vmatrix} a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-1}& a_{1,n} \\ 0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-1}& a_{2,n} \\ 0& 0& a_{3,3}&\cdots &a_{3,n-1}& a_{3,n} \\ \vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\ 0& 0&0&\cdots &a_{n-1,n-1}& a_{n-1,n} \\ 0& 0&0&\cdots &0& a_{n,n} \end{vmatrix} =a_{n,n}\times A_{n,n}=a_{n,n}\times (-1)^{2n}\times M_{n,n}=a_{n,n}\times M_{n,n} \]

注意到：

\[M_{n,n}= \begin{vmatrix} a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-2}& a_{1,n-1} \\ 0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-2}& a_{2,n-1} \\ 0& 0& a_{3,3}&\cdots &a_{3,n-2}& a_{3,n-1} \\ \vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\ 0& 0&0&\cdots &a_{n-2,n-2}& a_{n-2,n-1} \\ 0& 0&0&\cdots &0& a_{n-1,n-1} \end{vmatrix} \]

那么就有（下图的 \(A_{n-1,n-1}\) 和 \(M_{n-1,n-1}\) 是相对原矩阵去掉第 \(n\) 行第 \(n\) 列的子矩阵而言的）：

\[M_{n,n}= \begin{vmatrix} a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-2}& a_{1,n-1} \\ 0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-2}& a_{2,n-1} \\ 0& 0& a_{3,3}&\cdots &a_{3,n-2}& a_{3,n-1} \\ \vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\ 0& 0&0&\cdots &a_{n-2,n-2}& a_{n-2,n-1} \\ 0& 0&0&\cdots &0& a_{n-1,n-1} \end{vmatrix}=a_{n-1,n-1}\times A_{n-1,n-1} =a_{n-1,n-1}\times (-1)^{2n-2}\times M_{n-1,n-1}=a_{n-1,n-1}\times M_{n-1,n-1} \]

发现了什么？是的，我们可以继续递归下去求解，最终会得出：

\[\begin{vmatrix} a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-1}& a_{1,n} \\ 0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-1}& a_{2,n} \\ 0& 0& a_{3,3}&\cdots &a_{3,n-1}& a_{3,n} \\ \vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\ 0& 0&0&\cdots &a_{n-1,n-1}& a_{n-1,n} \\ 0& 0&0&\cdots &0& a_{n,n} \end{vmatrix} =\prod_{i=1}^na_{i,i} \]

因此上三角矩阵的行列式是非常好求的，重点又回到了将原矩阵消元为上三角矩阵的过程。

注意到题目中 \(p\) 不一定是质数，这就代表不一定所有 \(a_{i,j}\) 都有逆元，不能使用高斯消元，应该采用其他方式。

回忆 \(\gcd\) 的辗转相除法，最终一个数变为 \(\gcd\)，另外一个数则变为 0，是不是可以用来消元？

答案是肯定的。我们选定需要消元的那一行，与其他行做辗转相除。因为辗转相除所用的操作都是矩阵的初等变换，所以根据消元后的矩阵的行列式可以运用性质 1、3、5 很方便计算出原矩阵的行列式。

最后看一下算法的时间复杂度。消元部分的时间复杂度为 \(O(n^3)\)；辗转相除的时间复杂度均摊，得到 \(O(n^2\log p)\)。所以算法总的时间复杂度记为 \(O(n^2(n+\log p))\)。另外由于消元过程中数据规模变小，所以消元部分常数也较小，对于 \(n=600\) 的数据和 \(2.0s\) 的时限是没问题的。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,a[610][610],res=1,w=1/*初等变换带来的系数*/,mod;
int main()
{
	scanf("%d%d",&n,&mod);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			while(a[i][i])//没消掉就继续消 
			{
				for(int rate=a[j][i]/a[i][i]/*“相除”，把商作为系数乘在第 i 行的元素上*/,k=i/*没消掉的元从 i 开始*/;k<=n;++k)
        		    a[j][k]=(a[j][k]-1ll*rate*a[i][k]%mod+mod)%mod;//在消掉 a[j][i] 的同时它的整行元素都要进行同样操作 
				swap(a[i],a[j]);//“辗转”
				w=-w;//计算系数 
			}
        	swap(a[i],a[j]);//“辗转” 
			w=-w;//计算系数 
		}
	for(int i=1;i<=n;i++)
		res=1ll*a[i][i]*res%mod;//计算上三角矩阵的行列式 
	res=(1ll*res*w%mod+mod)%mod;//一定要乘上系数！！！ 
	printf("%d",res);
	return 0;
}

由于本文写的时间跨度比较长，不可避免地存在错误和不足，欢迎大家指出！

标签：P7112,tau,ddots,题解,vmatrix,times,cdots,vdots
From： https://www.cnblogs.com/hadtsti/p/17537672.html

相关文章

  • 关于Azure-平台-Redhat-Linux-服务器时间同步的问题解决
    首先说明一下，关于Azure平台中国区，是没有RedhatLinux系统镜像的于是笔者这边是通过在Windows系统 Hyper-V管理器中安装完Redhat8.x操作系统后，最后将系统磁盘转换成转换为VHD格式然后经过一系列操作、最终在Azure平台上形成了自己的并且加固过的RedHatEnterpriseLinuxre......
  • 【题解】 [APIO2007] 动物园
    目录题目链接原题描述题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2提示题意概括思路历程1.与环相关2.设计状态代码实现题目链接原题描述[APIO2007]动物园题目描述新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个......
  • 洛谷题解——【模板】堆
    题目链接：【模板】堆【模板】堆题目描述给定一个数列，初始为空，请支持下面三种操作：给定一个整数\(x\)，请将\(x\)加入到数列中。输出数列中最小的数。删除数列中最小的数（如果有多个数最小，只删除\(1\)个）。输入格式第一行是一个整数，表示操作的次数\(n\)。接下来\(n\)......
  • 并发网络周测题解释版
    并发网络周测题【一】理论篇1.简述OSI七层协议OSI七层协议（OpenSystemsInterconnection）是一种用于计算机网络通信的参考模型。该模型将网络通信过程分解为七个不同的层次，每个层次负责特定的功能和任务，这有助于网络设备和应用程序之间的协作和互操作性。【1】物理层（Physica......
  • CF500C New Year Book Reading 题解
    这一题是一道比较复杂的贪心(对于本蒟蒻来说)假如两本书\(a\)和\(b\)，先看\(a\)再看\(b\)，那么我们开始的时候就把\(a\)放在上面。这样的话，我们看\(a\)时就不需要搬动\(b\)，看\(b\)的时候会搬动\(a\)。而一开始如果把放在上面，看\(a\)的时候需要搬动\(b\)，看\(b\)......
  • AtCoder Beginner Contest 308 题解
    https://atcoder.jp/contests/abc308/tasks_printA-NewScheme过水已隐藏。#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/hash_policy.hpp>usingnamespacestd;u......
  • [HNOI2008] 玩具装箱 题解
    很难得遇到细节题打码5分钟调试两小时感谢游老师送出的1.5h调试，感激(争取每天用我的代码训练老师的该题能力）细节/思路见注释#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;/*本题细节很多！！！1.注意要把‘0’放进去，否则'1'一直弹不出去，导致答案偏大2......
  • 题解 P8648【[蓝桥杯 2017 省 A] 油漆面积】
    怎么题解区全是扫描线，还有个\(O(n^3)\)暴力老哥。为防止误导新人，给个理论上稳过的\(O(n^2)\)解法。二维前缀和可以处理若干次单点加，最后若干次矩形查的问题。将其差分，即可处理若干次矩形加，最后若干次单点查的问题。于是我们使用差分将所有矩形加上，然后做一遍二维前缀和，即......
  • 「NOIP 模拟赛 20230707」T2 - 涂照片 题解
    题目大意原题有一个\(n+1\timesm+1\)的网格。对于每一行\(i\)，都要将左侧的一些格子\((i,1),(i,2),\ldots,(i,x)\)涂黑，其中\(x=k\)的概率为\(a_{i,k}\)。同理对于每一列\(j\)，都要将上方的一些格子\((1,j),(2,j),\ldots,(x,j)\)涂黑，其中\(x=k\)的概率为\(b_{k,......
  • P7561[JOISC 2021 Day2] 道路の建設案 (Road Construction) 题解
    P7561[JOISC2021Day2]道路の建設案(RoadConstruction)题解题目描述JOI国是一个\(x\timesy\)的二维平面，王国里有\(n\)个城镇，分别编号为\(1,2,\cdots,n\in[1,2.5\times10^5]\)，其中第\(i\)个城镇的坐标为\((x_i,y_i)\)。在JOI国，正计划修建连接两座城......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99