当前位置: 首页 > news >正文

数学章节总结

一、矩阵乘法

  • 介绍

一个 \(m \times n\)矩阵是一个由 \(m\)\(n\) 列元素排列成的矩形阵列。即形如:

\[A = \begin{bmatrix} a_{(1,1)} & a_{(1,2)} & \cdots & a_{(1,n)} \\ a_{(2,1)} & a_{(2,2)} & \cdots & a_{(2,n)} \\ \vdots & \vdots & \ddots & \vdots \\ a_{(m,1)} & a_{(m,2)} & \cdots & a_{(m,n)} \end{bmatrix} \text{} \]

假定矩阵中的元素 \(a_{(i,j)}\) 是整数(当然有时也可以矩阵套矩阵)。

两个大小分别为 \(m \times n\)\(n \times p\) 的矩阵 \(A, B\) 相乘的结果为一个大小为 \(m \times p\) 的矩阵。将结果矩阵记作 \(C\),则:

\[c_{(i,j)} = \sum_{k = 1}^{n} a_{(i,k)}\times b_{(k,j)} \text{\qquad($1 \le i \le m$, $1 \le j \le p$).} \]

而如果 \(A\) 的列数与 \(B\) 的行数不相等,则无法进行乘法。

可以验证,矩阵乘法满足结合律,即 \((A B) C = A (B C)\)

矩阵乘法不满足交换律,即两个不同的矩阵 \(A,B\)\(AB \ne BA\)

一个大小为 \(n \times n\) 的矩阵 \(A\) 可以与自身进行乘法,得到的仍是大小为 \(n \times n\) 的矩阵,记作 \(A^2 = A \times A\)。进一步地,还可以递归地定义任意高次方 \(A^k = A \times A^{k - 1}\),或称 \(A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ 次}}\)

特殊地,定义 \(A^0\) 为单位矩阵 \(I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}\),任何矩阵乘它的单位矩阵都等于它本身,单位矩阵类似于数乘里的 \(1\)

  • 矩阵快速幂

与整数的快速幂差不多。

\(A^k\),首先把 \(k\) 转成二进制,令 \(k=2^0\times x_0+2^1\times x_1+\cdots+2^t\times x_t\) ,则可将矩阵 \(A\)\(k\) 的每一个二进制位翻倍,当 \(x_i=1\) 时,把答案矩阵乘上 \(A\) 矩阵。

  • 时间复杂度:\(O(\log_2k)\)
inline node mul(node x,node y){node res;memset(res.w,0,sizeof res.w);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=1;k<=q;k++){res.w[i][j]=(res.w[i][j]+1ll*x.w[i][k]*y.w[k][j]%mod)%mod;}}}return res;
}
inline node ksm(node x,int b){node ans=x;while(b){if(b&1) ans=mul(ans,a); a=mul(a,a); b>>=1;}return ans;
}

二、高斯消元

  • 介绍

    可以看这篇题解,讲得很详细~

    题解:P3389 【模板】高斯消元法

  • 高斯-约旦消元法

    题解:P3389 【模板】高斯消元法

  • 时间复杂度:\(O(n^3)\)

//普通高斯消元
void Gauss(int n){for(int i=1;i<=n;i++){int x=i;for(int j=i+1;j<=n;j++){if(fabs(a[x][i])<fabs(a[j][i])) x=j;}if(fabs(a[x][i])<step){cout<<"No Solution";return 0;}if(i!=x) swap(a[i],a[x]);double sum=a[i][i];for(int j=i;j<=n+1;j++) a[i][j]/=sum;for(int j=i+1;j<=n;j++){sum=a[j][i];for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*sum;}}ans[n]=a[n][n+1];for(int i=n-1;i>=1;i--){ans[i]=a[i][n+1];for(int j=i+1;j<=n;j++) ans[i]-=a[i][j]*ans[j];}for(int i=1;i<=n;i++) printf("%.2lf\n",ans[i]);
}
//高斯-约旦消元法
void Gauss(int n){for(int i=1;i<=n;i++){int x=i;for(int j=i+1;j<=n;j++){if(fabs(a[j][i])>fabs(a[x][i])) x=j;}if(fabs(a[x][i])<eps){cout<<"No Solution";exit(0);}if(i!=x) swap(a[i],a[x]);double y=a[i][i];for(int j=i;j<=n+1;j++) a[i][j]/=y;for(int j=1;j<=n;j++){if(j==i) continue;y=a[j][i];for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*y;}}for(int i=1;i<=n;i++) printf("%.2lf\n",a[i][n+1]);
}

三、求最大公约数/最小公倍数 \((gcd/lcm)\)

  • 最大公约数:辗转相除法(普通欧几里得算法)

证明: \(\gcd(a,b)=\gcd(b,a\bmod b)\) .

\(a>b\)\(x=a\bmod b\)\(x\ne 0\),则 \(a=k\times b+x\)\(a,b,k,x\) 均为正整数)。

\(y\)\(a,b\) 的一个公约数,记作 \(y\mid a\)\(y\mid b\) .

\(m=a\div y\)\(n=b\div y\),则 \(m,n\in N\) .

\(x=a-k\times b\),∴ \(x\div y=a\div y-k\times b\div y=m-k\times n\) .

\(x\div y\in N\)\(y\mid x\) .

\(y\) 也是 \(b,a \bmod b\) 的公约数,

\(a,b\)\(b,a\bmod b\) 的公约数都相等,所以其最大公约数也相等,得证。

由于任何数与 \(0\) 的最大公约数都是它本身,所以当 \(b=0\) 的时候,直接返回 \(a\) 就好了。

  • 对于 \(b\) 的最终状态一定会为 \(0\) 的证明:

因为每次都把 \(\gcd(a,b)\) 转化成 \(\gcd(b,a\bmod b)\),且 \(0\le (a\bmod b)\le b-1\),所以 \(b\) 每次都会至少变小 \(1\),所以最后 \(b\) 一定会为 \(0\) .

  • 最小公倍数

\(lcm(a,b)=a\times b\div \gcd(a,b)\) .

int gcd(int a,int b){if(b) return gcd(b,a%b);return a;
}
int lcm(int a,int b){return 1ll*a*b/gcd(a,b);
}

四、扩展欧几里得算法 \((exgcd)\)

  • 裴蜀定理

\(a,b\) 是整数,且 \(\gcd(a,b)=d\),对于任意整数 \(x,y\)\(ax+by\) 都一定是 \(d\) 的倍数,特别地,一定存在整数 \(x,y\),使 \(ax+by=\gcd(a,b)\) 成立。重要推论:\(a,b\) 互质的充要条件是存在整数 \(x,y\) 使 \(ax+by=1\) .

  • \(exgcd\) —— 可用来求 \(ax+by\equiv\gcd(a,b)\) 的解。

现在开始解这个方程。

通过辗转相除法可以知道:

\[\gcd(a,b)=\gcd(b,a\bmod b) \]

假设有另一组解 \((x_2,y_2)\) 存在:

\[b\times x_2+(a\bmod b)\times y_2\equiv a\times x+b\times y\equiv 1 \]

\[∵a\bmod b=a-\lfloor\frac{a}{b}\rfloor\times b \]

\[∴b\times x_2+(a-\lfloor\frac{a}{b}\rfloor\times b)\times y_2\equiv a\times x+b\times y \]

变个形:

\[b\times x_2+a\times y_2-\lfloor\frac{a}{b}\rfloor\times b\times y_2\equiv a\times x+b\times y \]

\[a\times y_2+b\times (x_2-\lfloor\frac{a}{b}\rfloor \times y_2)\equiv a\times x+b\times y \]

可得:

\[x=y_2,y=x_2-\lfloor\frac{a}{b}\rfloor \times y_2 \]

问题变成了如何解出 \((x_2,y_2)\)

利用方程 \(b\times x_2+(a\bmod b)\times y_2\equiv a\times x+b\times y\),就有了 \(b,a\bmod b\) 这两个系数,继续利用上述方法,找到下一组解 \((x_3,y_3)\)

在这个过程中,\((a,b)\) 会不断被替换为 \((b,a\bmod b)\),最后一定会出现 \(x_n=\gcd(a,b),y_n=0\) .

综上,我们只需要不断找到一组 \(x_i,y_i\),然后不断把 \(x,y\) 替换为 \(x=y_i\)\(y=x_i-b\times \lfloor\frac{a}{b}\rfloor\times y_i\),这样执行 \(n\) 次,最后把 \(x_n\) 赋为 \(\gcd(a,b)\)\(y_n\) 赋为 \(0\),再递归回去即可求出 \(x,y\) 了。

  • 时间复杂度:\(O(\log_2 max(a,b))\)

时间复杂度证明:

每次都把 \(\gcd(a,b)\) 替换成 \(\gcd(b,a\bmod b)\)

\(a<b\) ,相当于交换 \(a,b\) .

\(b<\frac{a}{2}\),因为余数小于除数,所以 \(a\bmod b<b<\frac{a}{2}\) ,会把 \(a\) 缩小一半。

\(b=\frac{a}{2}\),那么 \(a\bmod b=0\),结束递归。

\(b>\frac{a}{2}\),那么 \(\lfloor\frac{a}{b}\rfloor=1\)\(\gcd(b,a\bmod b)\) 变成了 \(gcd(b,a-b)\)
因为 \(b>\frac{a}{2}\),所以 \(a-b<\frac{a}{2}\),也会把 \(a\) 缩小一半。得证。

void exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1,y=0;return;}ll xx,yy;exgcd(b,a%b,xx,yy);x=yy;y=xx-a/b*yy;
}
http://www.hskmm.com/?act=detail&tid=23157

相关文章:

  • 软件工程_作业一
  • CF VP 记录
  • LabVIEW与PLC 汽车驻车制动自动调整 - 实践
  • 04. 布局管理
  • 关于安装博客园皮肤中有关于配置音乐播放器的补充(awescnb)
  • AGC VP 记录 2
  • 2025 --【J+S 二十连测】-- 第四套 总结
  • Websocket+cpolar:如何轻松实现服务远程访问? - 教程
  • 如何用C语言实现5种基本的排序算法
  • 函数-装饰器基础知识+推导式
  • VUE - 实战 2
  • QBXT2025S刷题 Day1
  • 2025多校冲刺CSP模拟赛1(螳臂复活祭)
  • mobvista三月之旅(In Peking)
  • 大学生HTML期末大作业——HTML+CSS+JavaScript购物商城(草莓) - 指南
  • P6782 [Ynoi2008] rplexq
  • AT_agc040_b [AGC040B] Two Contests
  • AT_arc084_b [ABC077D] Small Multiple 题目分析
  • 287. 寻找重复数
  • 福州市 2025 国庆集训 Day2 前三题题解
  • 2025 年马赛克厂家 TOP 企业品牌推荐排行榜,陶瓷,游泳池,喷墨,冰裂,拼花,防滑,复古,家装马赛克推荐这十家公司!
  • oppoR9m刷Linux系统: 手动备份系统与基带IMEI/NVRAM/QCN
  • 原来你是这样的claude code aciton:没想象中好
  • 实用指南:【Python】正则表达式
  • FlareOn1 -- 5get_it
  • 2025 年阀门厂家 TOP 企业品牌推荐排行榜,管道阀门,气动,调节,电动执行器,生产,电磁,不锈钢,进口,耐高温阀门推荐这十家公司
  • 深入解析:Ceph 分布式存储学习笔记(二):池管理、认证和授权管理与集群配置(下)
  • tcp与udp 协议 - 摘星
  • 赛前训练4 extra 字典树
  • CF1450E Capitalism