一、矩阵乘法
-
介绍
一个 \(m \times n\) 的矩阵是一个由 \(m\) 行 \(n\) 列元素排列成的矩形阵列。即形如:
假定矩阵中的元素 \(a_{(i,j)}\) 是整数(当然有时也可以矩阵套矩阵)。
两个大小分别为 \(m \times n\) 和 \(n \times p\) 的矩阵 \(A, B\) 相乘的结果为一个大小为 \(m \times p\) 的矩阵。将结果矩阵记作 \(C\),则:
而如果 \(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)\) 的解。
现在开始解这个方程。
通过辗转相除法可以知道:
假设有另一组解 \((x_2,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;
}