差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest2 [2021/07/12 23:12]
lgwza [题解]
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest2 [2021/07/18 11:04] (当前版本)
jxm2001
@@ 行 95: / 行 95: @@
 	enter((ss-s[i]+mod)%mod);
 	return 0;
+}
+</code>
+</hidden>
+===== D. 方阵的行列式 =====
+==== 题意 ====
+给定一个模 998244353 （质数）意义下的 $n\times n$ 的方阵和 $Q$ 个修改操作。每个修改操作都修改方阵中某个元素为一个新的值。在每个修改操作后，输出方阵的行列式。
+数据范围：
+$1\le n,Q\le 500$
+（修改第 $x$ 行第 $y$ 列的元素为 $z$）$1\le x,y\le n,0\le z<998244353$。
+==== 题解 ====
+=== 前置知识 ===
+  - **Sherman-Morrison formula**: 假设 $A\in\mathbb{R}^{n\times n}$ 是可逆方阵，$u,v\in\mathbb{R}^n$ 是列向量，则 $A+uv^T$ 可逆当且仅当 $1+v^TA^{-1}u\ne 0$，此时有 $$
+(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}
+$$ 成立
+  - **定义**：在 $n$ 阶行列式中，划去元 $a_{ij}$ 所在的第 $i$ 行与第 $j$ 列的元，剩下的元不改变原来的顺序所构成的 $n-1$ 阶行列式称为元 $a_{ij}$ 的**余子式**，记作 $M_{ij}$。
+  - **定义**：$a_{ij}$ 的**代数余子式**：$A_{ij}=(-1)^{i+j}M_{ij}$。
+  - **定理**：当 $|A|\ne 0$ 时，$A^{-1}=\dfrac{1}{|A|}A^*$，其中 $A^*$ 的第 $(i,j)$ 元为 $A$ 的第 $(j,i)$ 元的代数余子式 $A_{ji}$。$A^*$ 称为 $A$ 的伴随方阵。
+  - **展开定理**：行列式 $\Delta$ 的值，等于它的任意一行各元分别乘以各自的代数余子式的乘积之和： $$
+\Delta=\sum_{j=1}^na_{ij}A_{ij}.
+$$ 注意：在按行展开的公式 $$
+\Delta=a_{i1}A_{i1}+\cdots+a_{ij}A_{ij}+\cdots+a_{in}A_{in}
+$$ 中，第 $i$ 行的各元的代数余子式 $A_{i1},\cdots,A_{in}$ 的值都由 $\Delta$ 中第 $i$ 行以外的元决定，与第 $i$ 行各元 $a_{i1},\cdots,a_{in}$ 无关。因此，在行列式 $\Delta$ 中将第 $i$ 行各元分别换成任意值 $x_1,\cdots,x_n$，得到的行列式 $\Delta(x_1,\cdots,x_n)$ 按第 $i$ 行展开式中的各代数余子式 $A_{i1},\cdots,A_{in}$ 仍与在 $\Delta$ 中相同。
+=== 算法步骤 ===
+  - 高斯消元法求 $A^{-1}$ 和 $|A|$，记 $A^{-1}=C=(c_{ij})$，复杂度 $O(n^3)$。
+  - 执行修改操作，将 $(x,y)$ 元修改为 $z$，改变量记为 $delta=z-a_{xy}$，改变后的矩阵记为 $A'=(a'_{ij})$。
+  - 计算修改后的行列式的值 $|A'|$，用定理 5 对第 $x$ 行按行展开来求，而由定理 4，$A'_{ij}=A_{ij}=|A|c_{ji}$，故 $\displaystyle |A'|=\sum_{j=1}^na'_{xj}|A|c_{jx}$。
+  - 令 $|A|=|A'|$，并用定理 1 计算 $(A')^{-1}$：令 $u=(0,\cdots,0,1,0,\cdots,0)^T$（第 $x$ 个分量为 1，其它分量为 0 的列向量），$v=(0,\cdots,0,delta,0,\cdots,0)^T$ （第 $y$ 个分量为 $delta$，其它分量为 0 的列向量），即可在 $O(n^2)$ 内算出 $(A')^{-1}=(A+uv^T)=A^{-1}-\dfrac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$。然后令 $C=A^{-1}=(A')^{-1},A=A'$。回到步骤 2，进行下一步修改操作，直至修改操作结束。
+故总时间复杂度 $O(n^3+Qn^2)$。
+<hidden 查看代码>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=505,mod=998244353;
+int A[N][N],B[N][2*N],C[N][N],D[N][N],E[N][N],F[N][N];
+int qpow(int x,int y){
+    int ret=1;
+    for(;y;x=1ll*x*x%mod,y>>=1)
+        if(y&1) ret=1ll*ret*x%mod;
+    return ret;
+}
+void Get_Inverse_1(int n,int& det){
+    det=1;
+    memset(B,0,sizeof(B));
+    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) B[i][j]=A[i][j];
+    for(int i=1;i<=n;i++) B[i][i+n]=1;
+    int times=0;
+    for(int i=1;i<n;i++){
+        if(B[i][i]==0){
+            times++;
+            int row=-1;
+            for(int j=i+1;j<=n;j++)
+                if(B[j][i]!=0){
+                    row=j;
+                    break;
+                }
+            if(row==-1) continue;
+            for(int k=i;k<=2*n;k++) swap(B[i][k],B[row][k]);
+        }
+        for(int j=i+1;j<=n;j++){
+            int m=1ll*B[j][i]*qpow(B[i][i],mod-2)%mod;
+            for(int k=i;k<=2*n;k++){
+                B[j][k]=(1ll*B[j][k]-1ll*m*B[i][k]%mod+mod)%mod;
+            }
+        }
+        det=1ll*det*B[i][i]%mod;
+    }
+    det=1ll*det*B[n][n]%mod;
+    if(times&1) det=(mod-det)%mod;
+    for(int i=n;i>=1;i--){
+        int temp=B[i][i];
+        temp=qpow(temp,mod-2);
+        B[i][i]=1;
+        for(int k=n+1;k<=2*n;k++) B[i][k]=1ll*B[i][k]*temp%mod;
+        int temp2=qpow(B[i][i],mod-2);
+        for(int j=i-1;j>=1;j--){
+            int m=1ll*B[j][i]*temp2;
+            for(int k=n+1;k<=2*n;k++){
+                B[j][k]=(1ll*B[j][k]-1ll*m*B[i][k]%mod+mod)%mod;
+            }
+        }
+    }
+    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) C[i][j]=B[i][j+n];
+}
+int C2[N],C3[N];
+void Get_Inverse_2(int n,int x,int y,int delta){
+    int deno=(1+1ll*C[y][x]*delta%mod)%mod;
+    deno=qpow(deno,mod-2);
+    for(int i=1;i<=n;i++) C2[i]=C[i][x],C3[i]=C[y][i];
+    for(int i=1;i<=n;i++){
+        for(int j=1;j<=n;j++)
+            C[i][j]=(1ll*C[i][j]-1ll*C2[i]*delta%mod*C3[j]%mod*deno%mod+mod)%mod;
+    }
+}
+int main(){
+    int n,q;
+    scanf("%d%d",&n,&q);
+    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&A[i][j]);
+    int det;
+    Get_Inverse_1(n,det);
+    while(q--){
+        int x,y,z;
+        scanf("%d%d%d",&x,&y,&z);
+        int before=A[x][y];
+        A[x][y]=z;
+        int ans=0;
+        for(int j=1;j<=n;j++){
+            ans=(1ll*ans+1ll*A[x][j]*C[j][x]%mod*det%mod)%mod;
+        }
+        printf("%d\n",ans);
+        det=ans;
+        int delta=(z-before+mod)%mod;
+        Get_Inverse_2(n,x,y,delta);
+    }
+    return 0;
 }
 </code>
@@ 行 164: / 行 293: @@
 </code>
 </hidden>
-===== D. 方阵的行列式 =====
-==== 题意 ====
-给定一个模 998244353 （质数）意义下的 $n\times n$ 的方阵和 $Q$ 个修改操作。每个修改操作都修改方阵中某个元素为一个新的值。在每个修改操作后，输出方阵的行列式。
-数据范围：
-$1\le n,Q\le 500$
-（修改第 $x$ 行第 $y$ 列的元素为 $z$）$1\le x,y\le n,0\le z<998244353$。
-==== 题解 ====
-=== 前置知识 ===
-  - **Sherman-Morrison formula**: 假设 $A\in\mathbb{R}^{n\times n}$ 是可逆方阵，$u,v\in\mathbb{R}^n$ 是列向量，则 $A+uv^T$ 可逆当且仅当 $1+v^TA^{-1}u\ne 0$，此时有 $$
-(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}
-$$ 成立
-  - **定义**：在 $n$ 阶行列式中，划去元 $a_{ij}$ 所在的第 $i$ 行与第 $j$ 列的元，剩下的元不改变原来的顺序所构成的 $n-1$ 阶行列式称为元 $a_{ij}$ 的**余子式**，记作 $M_{ij}$。
-  - **定义**：$a_{ij}$ 的**代数余子式**：$A_{ij}=(-1)^{i+j}M_{ij}$。
-  - **定理**：当 $|A|\ne 0$ 时，$A^{-1}=\dfrac{1}{|A|}A^*$，其中 $A^*$ 的第 $(i,j)$ 元为 $A$ 的第 $(j,i)$ 元的代数余子式 $A_{ji}$。$A^*$ 称为 $A$ 的伴随方阵。
-  - **展开定理**：行列式 $\Delta$ 的值，等于它的任意一行各元分别乘以各自的代数余子式的乘积之和： $$
-\Delta=\sum_{j=1}^na_{ij}A_{ij}.
-$$ 注意：在按行展开的公式 $$
-\Delta=a_{i1}A_{i1}+\cdots+a_{ij}A_{ij}+\cdots+a_{in}A_{in}
-$$ 中，第 $i$ 行的各元的代数余子式 $A_{i1},\cdots,A_{in}$ 的值都由 $\Delta$ 中第 $i$ 行以外的元决定，与第 $i$ 行各元 $a_{i1},\cdots,a_{in}$ 无关。因此，在行列式 $\Delta$ 中将第 $i$ 行各元分别换成任意值 $x_1,\cdots,x_n$，得到的行列式 $\Delta(x_1,\cdots,x_n)$ 按第 $i$ 行展开式中的各代数余子式 $A_{i1},\cdots,A_{in}$ 仍与在 $\Delta$ 中相同。
 ====== 赛后总结 ======
 jxm：感觉有一半的时间在 debug
+wza：代码能力需要加强

CVBB ACM Team

用户工具

站点工具

差别

页面工具