基本矩阵/消元复习

模板有标记

目录

• P3390【矩阵快速幂】
• P6772
• P5303
• P3389【高斯消元】
• P2455【高斯消元（判无解）】
• P4783【矩阵求逆】
• P4035

---

P3390【矩阵快速幂】

【记录】

P6772

拆点， 把每个点 x 拆成几个形如 “还有 k 秒到达点 x” 的点， 就可以用矩阵表示转移了。

由于中间要插入几次美食节， 所以把转移矩阵预处理出来， 到时候直接用。

【记录】

Tabsize = 1 配合高挑的字体可以获得超神的代码观感。

P5303

首先可以发现必然是一个完整的 (2 imes Kquad (Kge 3)) 的长条的两端包容了那两个 (1 imes1) 的格子， 否则可以证明不能完整地填完 (2 imes N) 的空间。

且如果 (K) 是奇数， 那么 (1 imes1) 的格子异行，反之同行。

设 (f_i) 表示 (N = i) 时的答案， (g_i) 表示 (2 imes i) 的空间只用 (1 imes2) 的格子覆盖的答案， (hat g_i) 表示 (sumlimits_{0le jle i} g_j)， 那么有：

[f_i = f_{i-1}+f_{i-2}+2hat g_{i-3} ]

(g) 实际上就是斐波那契数列， (g_2=2)。

故有结论：(hat g_i = g_{i+2} - 1)。

所以有：

[f_i = f_{i-1}+f_{i-2}+2g_{i-1}-2 ]

[left[ egin{matrix} 1&1&2&2&-2\ 1&0&0&0&0\ 0&0&1&1&0\ 0&0&1&0&0\ 0&0&0&0&1 end{matrix} ight] imes left| egin{matrix} f_i\ f_{i-1}\ g_{i-1}\ g_{i-2}\ 1 end{matrix} ight| ]

【记录】

P3389【高斯消元】

朴素写消元代码太难看， 把矩阵的初等变换写成函数会好看许多。

【记录】

P2455【高斯消元（判无解）】

相比模板增加了判无解的情况。

用高斯-约旦消元。

【记录】

P4783【矩阵求逆】

由于矩阵的初等变换可以表示成矩阵乘法的形式， 所以把一个矩阵用矩阵初等变换变成单位矩阵，就相当于给它乘上它的逆矩阵。

把这些变换无损施加到另一个单位矩阵上，就可以得到这个矩阵的逆矩阵。

【记录】

P4035

设中点为 (p)， 有某个在球面上的点 (x)， 球的半径为 (R)，那么：

[(x_1-p_1)^2+(x_2-p_2)^2+cdots+(x_n-p_n)^2 = R^2 ]

把 ((x_i-p_i)^2) 拆开得到 (x_i^2 + p_i^2 - 2x_ip_i)。

由于有 (n+1) 个球面上的点， 所以上面那个等式也有 (n+1) 个， 把前 (n) 个等式都减去第 (n+1) 个等式， 就得到：

[sum_{i=1}^n (x_i^2+p_i^2-2x_ip_i)-(x_{n+1,i}^2+p_i^2-2x_{n+1,i}p_i) = 0\ sum_{i=1}^n2(x_{n+1,i}-x_i)p_i = sum_{i=1}^n (x_{n+1,i}^2-x_i^2) ]

然后就可以高斯消元了。

光解方程还是推荐高斯-约旦消元。

【记录】