矩阵

行列式

(;)
转置后行列式不变((A_{i,j}=A'_{j,i}))
一行加上另一行的若干倍，行列式不变
交换两行，行列式变为原先的相反数
(;)
范德蒙德行列式

[ D_n = egin{vmatrix} 1 & 1 & 1 & cdots & 1 \ x_1 & x_2 & x_3 & cdots & x_n \ vdots & vdots & vdots & ddots & vdots \ x_1^{n-1} & x_2^{n-1} & x_3^{n-1} & cdots & x_n^{n-1} \ end{vmatrix} = prod_{1leq i<jleq n} (x_j-x_i) ]

证明：首先每一行加上上一行的(-x_n)倍
这样使得最后一列除了第一行是1以外，其余都变成0

[D_n=(-1)^{n+1} imes (x_1-x_n) imes (x_2-x_n) imes ... imes (x_{n-1}-x_n) D_{n-1} ]

[=prod_{1leq i<jleq n} (x_j-x_i) ]

NOI2021 Day1 T2

(;)
(k=2)
一个点不能同时匹配两个点，且答案和逆序对的奇偶性有关，联想到行列式
直接求邻接矩阵的行列式就是答案
(;)
(k>2)
对于两条路径，容易发现，它们交点的个数只与起点和终点有关，与中间怎么走没有关系（这个可以记一下）
所以假如说求出来了(f_{i,j})表示从(s_i)走到(t_j)的方案数
也是让一个(i)唯一匹配一个(j)
只需要对(f)求行列式
(;)
等等，好像有一些不对劲。这样并不保证两条路径不重复经过同一个点啊。
想想发现，假如我们把路径翻转过来，即：
原先是(s_i -> t_i, s_j -> t_j)
现在是(s_i -> t_j, s_j -> t_i)
且是一奇一偶，那么在计算行列式的时候就会把这两种都不合法的方案抵消掉

NOI2021 Day2 T2

(;)
怎么总是T2考矩阵啊。。。
容易发现，计算答案的操作相当于不断对结尾的数取倒数，然后累加到上一个数上
初始时：(1)与(a_n)肯定是互质的，对于(frac{y}{z})，累加到(x)上，得到：(frac{xz+y}{z})，容易发现，这个分数分子分母也是互质的
因此就不用管互质的问题了，对于分子分母分开考虑
如果把答案看作一个矩阵：那么也可以把每个操作写成矩阵乘法的形式（感觉这个东西其实挺套路的）
累加：
$
egin{bmatrix}

end{bmatrix}
$