网站开发 网页设计,试题wordpress的特点,代理域名网站的公司,室内装修设计书籍前置知识#xff1a;矩阵、高斯消元 行列式 行列式定义 \[\text{det(A)}\sum_{p}{(-1)^{\mathrm{sgn}(p)}\prod{A_{i,p_i}}} \]其中 \(\text{sgn}(p)\) 表示排列 \(p\) 的逆序对个数。 行列式性质 进行一次矩阵转职#xff0c;行列式不变。(易证)行列式任意一行按比例扩大矩阵、高斯消元 行列式 行列式定义 \[\text{det(A)}\sum_{p}{(-1)^{\mathrm{sgn}(p)}\prod{A_{i,p_i}}} \]其中 \(\text{sgn}(p)\) 表示排列 \(p\) 的逆序对个数。 行列式性质 进行一次矩阵转职行列式不变。(易证)行列式任意一行按比例扩大行列式的值按同样比例扩大。(易证)行列式中交换任意两行行列式反号。(易证)行列式中若有两行成比例则行列式值为 \(0\)。(通过第二条证明)行列式中若有一行可以表示为两个数列相加则行列式为两个行列式的值的和。(证明如下) \[\text{det}(A)\sum_p(-1)^{\mathrm{sgn}(p)}\times(B_{k,p_k}C_{k,p_k})\times \prod_{i1}^{n~\text{and}~i\notk}{a_{i,p_i}}\mathrm{det}(B)\mathrm{det}(C) \]行列式求值 P7112 【模板】行列式求值 根据上面五条性质可以将矩阵一步步消为左下角全是 \(0\) 的举证类似于高斯消元。最后将矩阵的对角线乘起来即可。 nrd(),modrd();
for(int i1;in;i) for(int j1;jn;j) a[i][j]rd()%mod;
for(int i1;in;i)
{for(int ji1;jn;j){while(a[j][i]){ll tmpa[i][i]/a[j][i];for(int ki;kn;k)a[i][k](a[i][k]-tmp*a[j][k]%modmod)%mod;swap(a[i],a[j]),w-w;}}
}
for(int i1;in;i) ansans*a[i][i]%mod;
printf(%lld\n,(modw*ans)%mod); LGV 引理(Lindstrom-Gessel-Viennot lemma) LGV 引理 内容 \(G\) 是一个有限的带权有向无环图。每个顶点的度是有限的不存在有向环(所以路径数量是有限的)。起点 \(A\{a_1,\cdots,a_n\}\)终点 \(B\{b_1,\cdots,b_n\}\)。每条边 \(e\) 有边权 \(\omega_e\)。对于一个有向路径 \(P\)定义 \(\omega(P)\) 为路径上所有边权的积。对任意顶点 \(a,b\)定义 \(e(a,b)\sum\limits_{P:a \to b}{\omega(P)}\)所有 \(a\) 到 \(b\) 的路径的 \(\omega\) 之和。 设矩阵 \[M{\begin{pmatrix}e(a_{1},b_{1})e(a_{1},b_{2})\cdots e(a_{1},b_{n})\\e (a_{2},b_{1})e(a_{2},b_{2})\cdots e(a_{2},b_{n})\\\vdots \vdots \ddots \vdots \\e(a_{n},b_{1})e(a_{n},b_{2})\cdots e(a_{n},b_{n})\end{pmatrix}} \]从 \(A\) 到 \(B\) 的不相交路径组 \(P(P_1,P_2,\cdots,P_n)\)\(P_i\) 表示从 \(a_i\) 到 \(b_{\sigma(i)}\) 的一条路径其中 \(\sigma\) 是一个排列(反映了这个排列的映射关系)并且满足对任意 \(i\notj\)\(P_i\) 与 \(P_j\) 没有公共点。记 \(\sigma(P)\) 表示 \(P\) 对应 \(B\) 的排列。 引理说明\(M\) 的行列式是所有从 \(A\) 到 \(B\) 的不相交路径 \(P(P_1,\cdots,P_n)\) 的带符号和。 \[\mathrm{det}(M)\sum_{P:A\to B}{(-1)^{\mathrm{sgn}(\sigma(P))}\prod_{i1}^{n}\omega(P_i)} \]证明 反证法即只需证明(其中 \(P:A\rightarrow B\)存在 \(i\notj\)\(P_i\) 与 \(P_j\) 有交点) \[\mathrm{det}(M)\sum_{P:A\rightarrow B}(-1)^{\mathrm{sgn}(\sigma(P))}\prod_{i1}^{n}{\omega(P_i)}0 \]假设存在一个 \(P\)其中 \(P_i\) 与 \(P_j\) 相交则 \(a_i\rightarrow b_{\sigma(i)}\) 与 \(a_j\rightarrow b_{\sigma(j)}\) 相交。那么我们将 \(b_{\sigma(i)}\) 与 \(b_{\sigma(j)}\) 互换最后答案不变而奇偶性相反一定存在 \(P-P\)。因此如果这一组路径有交点那么一定被抵消原命题得证。 应用 P6657 【模板】LGV 引理 由于在网格上如果 \(\sigma\not(1,2,\cdots,n)\)则显然没有解。 因此直接 \[\text{det}(M)\sum_{P:A\rightarrow B}{1} \]构造矩阵\(e(a_i,b_j)\binom{b_j-a_in-1}{n-1}\) 后求行列式即可。 P7736 [NOI2021] 路径交点 乍一眼好像就是 LGV 模型。 就是每一次的 \(\sigma(P)\) 变为了每一层的点对但是发现最终的排列方式的逆序对数的奇偶性和中间怎样连接没有关系所以可以直接 \((-1)^{\mathrm{sgn}(\sigma(P)}\)似乎就做完了。 矩阵树定理 咕咕咕
