可以做围棋题的网站,wordpress搬站流程,python做网站难么,怎么做网站邮箱目录 一、前置知识#xff1a;向量#xff08;一列或一行的矩阵#xff09;、矩阵1. 行向量2. 列向量3. 向量其余基本概念4. 矩阵基本概念5. 关于它们的细节 二、运算1. 转置#xff08;1#xff09;定义#xff08;2#xff09;性质 2. 矩阵#xff08;向量#xff0… 目录 一、前置知识向量一列或一行的矩阵、矩阵1. 行向量2. 列向量3. 向量其余基本概念4. 矩阵基本概念5. 关于它们的细节 二、运算1. 转置1定义2性质 2. 矩阵向量与矩阵向量的加减法3. 点乘与乘法1定义矩阵点乘2定义向量点乘3定义矩阵向量与标量的乘法4定义矩阵向量与矩阵向量的乘法5性质矩阵向量与矩阵向量的乘法6应用矩阵快速幂进行加速 三、拓展1. 向量表示里的几何意义2. 向量加法里的几何意义3. 向量求反里的几何意义 四、结尾 一、前置知识向量一列或一行的矩阵、矩阵
1. 行向量
例如 [ 1 1 4 ] \begin{bmatrix}114\end{bmatrix} [114]这就是一个行向量 [ 1 1 4 ] \begin{bmatrix}114\end{bmatrix} [114]可以理解为一个 1 1 1行 3 3 3列矩阵。
行向量 [ a 1 … a n ] \begin{bmatrix}a_1\dotsa_n\end{bmatrix} [a1…an] n n n为任意取值。
2. 列向量
例如 [ 5 1 4 ] \begin{bmatrix}5\\1\\4\end{bmatrix} 514 这就是一个列向量 [ 5 1 4 ] \begin{bmatrix}5\\1\\4\end{bmatrix} 514 可以理解为一个 3 3 3行 1 1 1列的矩阵。
列向量 [ a 1 ⋮ a n ] \begin{bmatrix}a_1\\\vdots\\a_n\end{bmatrix} a1⋮an n n n为任意取值。
3. 向量其余基本概念
向量是一个有方向与大小的量它的起点可以是任意位置。
维度 [ a 1 ] \begin{bmatrix}a_1\end{bmatrix} [a1]这是一个一维向量它仅有一个数字。而 [ a 1 ⋮ a n ] \begin{bmatrix}a_1\\\vdots\\a_n\end{bmatrix} a1⋮an 与 [ a 1 … a n ] \begin{bmatrix}a_1\dotsa_n\end{bmatrix} [a1…an]它们都是 n n n维的。
长度 向量的长度也就是它的大小我们称它为模。而模则为向量起点与终点之间的距离。
4. 矩阵基本概念 [ 1 1 4 1 6 1 4 1 5 ] \begin{bmatrix}114\\161\\415\end{bmatrix} 114161415 注 这是一个维度为 3 × 3 3\times3 3×3的矩阵。
一个矩阵的维度表示为 m × n m\times n m×n即 m m m行 n n n列的矩阵。
5. 关于它们的细节
向量可以视为一种特殊的矩阵我们通常用大写字母表示矩阵小写字母表示向量可带一个小箭头例如 v ⃗ \vec{v} v 。例如 v i v_i vi表示向量 v v v的第 i i i项即第 i i i个元素行向量从左往右数列向量从上往下 a i , j a_{i,j} ai,j或 A i , j A_{i,j} Ai,j表示矩阵 A A A的第 i i i行第 j j j列的元素。
二、运算
下文由于向量可以视为一种特殊的矩阵且为了方便所以均用大写字母表示向量或矩阵。
1. 转置
1定义 A T A^T AT表示对 A A A进行转置即 A A A的第 i i i行将变成 A T A^T AT的第 i i i列。若 A [ 1 1 4 5 1 4 ] A\begin{bmatrix}114\\514\end{bmatrix} A[151144]则 A T [ 1 5 1 1 4 4 ] A^T\begin{bmatrix}15\\11\\44\end{bmatrix} AT 114514 。
2性质 ( A T ) T A (A^T)^TA (AT)TA ( A B ) T A T B T (AB)^TA^TB^T (AB)TATBT
2. 矩阵向量与矩阵向量的加减法
我们设 A ± B C A\pm BC A±BC。 A ± B A\pm B A±B不是随便的 A A A与 B B B要求维度相同。且 C C C维度仍与 A A A、 B B B相同。 运算方式 C i , j A i , j ± B i , j C_{i,j}A_{i,j}\pm B_{i,j} Ci,jAi,j±Bi,j。
3. 点乘与乘法
1定义矩阵点乘
我们设 A ∘ B C A\circ BC A∘BC。
矩阵点乘的符号为“ ∘ \circ ∘”其中 A A A、 B B B、 C C C均为矩阵且维度相同。运算方法也很简单 C i , j A i , j × B i , j C_{i,j}A_{i,j}\times B_{i,j} Ci,jAi,j×Bi,j。
2定义向量点乘
我们再设 A ⋅ B n A\cdot Bn A⋅Bn。
显然 A A A、 B B B均为向量且维度相同而 n n n又是一个标量。那 n n n为多少 n ∑ i 1 m A i , j B i , j n\sum_{i1}^mA_{i,j}B_{i,j} n∑i1mAi,jBi,j m m m为 A A A、 B B B的维度。
3定义矩阵向量与标量的乘法
我们再设 n A B nAB nAB。
则 A A A、 B B B为矩阵向量 n n n为标量显而易见 B i , j n A i , j B_{i,j}nA_{i,j} Bi,jnAi,j。
4定义矩阵向量与矩阵向量的乘法
我们再再设 A B C ABC ABC设 A A A维度为 m × n m\times n m×n而 B B B维度为 n × p n\times p n×p则 C C C维度为 m × p m\times p m×p。
运算方式大概如此复杂 C i , j A i 行 ⋅ B j 列 C_{i,j}A_{i行}\cdot B_{j列} Ci,jAi行⋅Bj列即 C i , j ∑ i 1 n A i , k B k , j C_{i,j}\sum_{i1}^nA_{i,k}B_{k,j} Ci,j∑i1nAi,kBk,j。
5性质矩阵向量与矩阵向量的乘法
没有交换律。有结合律和分配率。
6应用矩阵快速幂进行加速
现在目光转置P1962要运用矩阵乘法来解决求斐波那契数列第 n n n项对 1 0 9 7 10^97 1097取模。
我们构造一个矩阵 A A A与矩阵 B B B A [ x y ] A\begin{bmatrix}xy\end{bmatrix} A[xy] B [ 1 1 1 0 ] B\begin{bmatrix}11\\10\end{bmatrix} B[1110]而 A B [ x y x ] AB\begin{bmatrix}xyx\end{bmatrix} AB[xyx]。现在设 x x x是斐波那契数列的第 ( i 1 ) (i1) (i1)项简记 F i 1 F_{i1} Fi1 y y y则为第 i i i项简记 F i F_i Fi。再把目光转回矩阵 A [ F i 1 F i ] A\begin{bmatrix}F_{i1}F_i\end{bmatrix} A[Fi1Fi] 则 A B [ F i 1 F n F i 1 ] AB\begin{bmatrix}F_{i1}F_nF_{i1}\end{bmatrix} AB[Fi1FnFi1]根据斐波那契数列的规律 F i 1 F i F i 2 F_{i1}F_iF_{i2} Fi1FiFi2so A B [ F i 2 F i 1 ] AB\begin{bmatrix}F_{i2}F_{i1}\end{bmatrix} AB[Fi2Fi1]很容易发现 A B AB AB比 A A A中每项都进了一位也就是说只要一直乘 B B B直至结果矩阵为 [ F n F n − 1 ] \begin{bmatrix}F_nF_{n-1}\end{bmatrix} [FnFn−1]第一项就是P1962的答案。
但是直接递推到 F n F_n Fn是 O ( n ) O(n) O(n)的乘到 F n F_n Fn也是 O ( n ) O(n) O(n)的。但是多个相同数相乘是数的幂多个相同矩阵相乘是矩阵的幂同样也可以使用快速幂现在复杂度大约为 O ( k l o g 2 n ) O(klog_2n) O(klog2n)有些小细节没有提及 k k k为矩阵乘法运算时耗掉的。这时当 n n n的值到达一个程度时间就会大幅减少。
代码如下。
#includebits/stdc.h
using namespace std;
#define ll long long
const ll p1e97;
struct mat{ll nr,nc;ll m[15][15];mat(ll NR0,ll NC0){nrNR,ncNC;memset(m,0,sizeof(m));}mat operator(mat b){nrb.nr;ncb.nc;for(int i1;inr;i)for(int j1;jnc;j)m[i][j]b.m[i][j];}
};
mat operator*(mat a,mat b){mat c(a.nr,b.nc);for(int i1;ia.nr;i){for(int j1;jb.nc;j){for(int k1;ka.nc;k){c.m[i][j](a.m[i][k]*b.m[k][j]%pc.m[i][j])%p;}}}return c;
}
mat fastpow(mat a,ll b){if(b1)return a;if(b%20)return fastpow(a*a,b/2);else return fastpow(a*a,b/2)*a;
}
int main(){ll n;cinn;if(n2){cout1;return 0;}mat fib(1,2),tmp(2,2),tmp2;fib.m[1][1]1,fib.m[1][2]1;tmp.m[1][1]1,tmp.m[1][2]1;tmp.m[2][1]1;tmp2fib*fastpow(tmp,n-2);couttmp2.m[1][1];
}三、拓展
1. 向量表示里的几何意义
例如有一个二维向量 v ⃗ [ x y ] \vec{v}\begin{bmatrix}x\\y\end{bmatrix} v [xy]它将原点 ( 0 , 0 ) (0,0) (0,0)作为起点时它的终点就是 ( x , y ) (x,y) (x,y)。
2. 向量加法里的几何意义 如图向量 a a a与向量 b b b头尾相接最终与向量 c c c到达同一目的地而恰好 a ⃗ b ⃗ c ⃗ \vec{a}\vec{b}\vec{c} a b c 。
3. 向量求反里的几何意义 a ⃗ \vec{a} a 与 − a ⃗ -\vec{a} −a 的区别在于将 a ⃗ \vec{a} a 旋转 180 ° 180\degree 180°就可以得 − a ⃗ -\vec{a} −a 即方向相反。
四、结尾
