线性代数
线性
对于函数 \(f(x)\)（在实数域上）是线性的，当且仅当：对于任意 \(x,y,c\)，有 \(f(x+y)=f(x)+f(y)\) 和 \(f(cx)=cf(x)\)。
定义域和值域：\(c\) 是“数”，\(x\) 和 \(f(x)\) 均为“可运算的元素”
向量表示与矩阵
向量
向量 \(\vec{v}\)，是一个纵向的列表，列表的每个元素都是一个数。有时也可称作列向量，并把向量的长度称为向量的维数。
可以用一个 \(n\) 维向量描述一个对象的 \(n\) 个属性。
向量加法：
\(\vec{u}+\vec{v}=\begin{bmatrix}u_1 \\u_2 \\\vdots \\u_n \end{bmatrix}+\begin{bmatrix}v_1 \\v_2 \\\vdots \\v_n \end{bmatrix}=\begin{bmatrix}u_1+v_1 \\u_2 +v_2\\\vdots \\u_n+v_n \end{bmatrix}\)
向量数乘：
\(c\vec{v}=c\begin{bmatrix}v_1 \\v_2 \\\vdots \\v_n \end{bmatrix}=\begin{bmatrix}cv_1 \\cv_2 \\\vdots \\cv_n \end{bmatrix}\)
线性函数的形式：
若函数 \(f\) 满足 \(f(\vec{u})+f(\vec{v})=f(\vec{u}+\vec{v})\) 和 $
线性变换
矩阵表示
- 找出转移所需的全部元素，列到一个向量里
- 考虑转移
- 矩阵快速幂优化
- Problem 1
计算连分数，单点修改+查询。
- Problem 2
给定三个长度为 \(n\) 的序列 \(a,b,sum\)，初始全为 \(0\)，要求支持区间 \(a_i+=c,b_i+=c,sum_i+=a_i\times b_i\)，查询 \(sum\) 区间和。
用线段树在每个下标处维护一个向量，转移向量为 \(\begin{bmatrix}1 \\a_i \\b_i \\a_ib_i \\sum_i \end{bmatrix}\)
线段树维护五阶矩阵 \(O(125 n \log n)\)，考虑优化。
注意到该矩阵是一个下三角矩阵，只枚举满足 \(i\le j\le k\) 的下标，优化为 \(O(35 n \log n)\)。
注意到矩阵中有许多的无效项（对角线、\(a_i\) 对 \(b_i\) 的值永远是 \(0\))，因此可以跳过，变为四阶矩阵，优化为近 \(O(10n \log n)\)。
- P7739
太难了，不适合我 qwq，咕咕咕。
\(\begin{bmatrix}a_{11} & a_{12} & \cdots & a_{1n} \\a_{21} & a_{22} & \cdots & a_{2n} \\\vdots & \vdots & \ddots & \vdots \\a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}\)
