长春网站设计哪家好,北美购物网站排名,企业云网站建设,seo优化公司哪家好线性基
导入
线性基#xff0c;顾名思义#xff0c;就是一个包含数字最少的集合#xff0c;使得原集合中的任何数都能用线性基中的元素表示。
集合中的元素满足一些性质#xff1a;
原集合中的任意元素都可以用线性基中的若干元素的异或和表示线性基中任意数异或和不为…线性基
导入
线性基顾名思义就是一个包含数字最少的集合使得原集合中的任何数都能用线性基中的元素表示。
集合中的元素满足一些性质
原集合中的任意元素都可以用线性基中的若干元素的异或和表示线性基中任意数异或和不为 0 0 0否则不满足集合大小最小以任意顺序枚举原集合中元素所得集合大小相同大小为 n n n 的线性基可以表示 2 n 2^n 2n 个数若线性基中存在二进制第 i i i 位为 1 1 1 的数则可以表示 2 n − 1 2^{n-1} 2n−1 个二进制下第 i i i 位为 1 1 1 的数。
操作
插入
我们用数组 p 表示线性基假设要插入 x x x从高到低枚举 x x x 的二进制的每一位数字如果 x x x 的第 i i i 位为 1 1 1 且 p i 0 p_i0 pi0那么令 p i x p_ix pix 并结束插入否则令 x^p[i]继续枚举下一位。
void insert(int x)
{for(int i50;i0;--i)if(xi1){if(!p[i]) {p[i]x;break;}else x^p[i];}
}求异或最大值
求原集合的子集的异或最大值利用贪心思想。若 ans^p[i]ans则 ans^p[i]。
int pmax()
{int ans0;for(int i50;i0;--i)if((ans^p[i])ans) ans^p[i];return ans;
}求异或最小值
分两种情况考虑
线性基大小 原集合大小原集合中一定存在异或和为 0 0 0 的一些数所以异或最小值为 0 0 0。线性基大小 原集合大小在线性基内求异或最小值线性基内的最小元素与其他元素异或得到的值一定更大所以异或最小值为线性基中最小元素。 剩的异或 k k k 小值先咕了 QwQ 本来学线性基是想过 YbtOJ 的最大异或对的结果发现线性基是任意数的最大异或和这一道题是一对只能用 trie 树 练手板子题
代码如下
#include bits/stdc.h
using namespace std;
#define int long longint p[55];void insert(int x)
{for(int i50;i0;--i)if(xi1){if(!p[i]) {p[i]x;break;}else x^p[i];}
}int pmax()
{int ans0;for(int i50;i0;--i)if((ans^p[i])ans) ans^p[i];return ans;
}signed main()
{int n,x;cinn;for(int i1;in;i) cinx,insert(x);coutpmax();return 0;
}行列式
行列式是一种对于矩阵的特殊形式——方阵的表示形式。所谓方阵就是 n × n n\times n n×n的矩阵。
一个 n × n n\times n n×n 的方阵 A A A 的行列式记为 det ( A ) \det(A) det(A) 或者 ∣ A ∣ |A| ∣A∣一个 2 × 2 2\times2 2×2 矩阵的行列式可表示如下 det ( a b c d ) a d − b c \det \begin{pmatrix} ab\\ cd \end{pmatrix}ad-bc det(acbd)ad−bc 把一个 n n n 阶行列式中的元素 a i j a_{ij} aij 所在的第 i i i行和第 j j j列划去后留下来的 n − 1 n-1 n−1 阶行列式叫做元素 a i j a_{ij} aij 的余子式记作 M i j M_{ij} Mij。记 A i j ( − 1 ) i j M i j A_{ij}(-1)^{ij}M_{ij} Aij(−1)ijMij叫做元素 a i j a_{ij} aij 的代数余子式。
一个 n × n n\times n n×n 矩阵的行列式等于其任意行或列的元素与对应的代数余子式乘积之和即 det ( A ) a i 1 A i 1 ⋯ a i n A i n ∑ j 1 n a i j ( − 1 ) i j det ( A i j ) \det(A)a_{i1}A_{i1}\cdotsa_{in}A_{in}\sum_{j1}^na_{ij}(-1)^{ij}\det(A_{ij}) det(A)ai1Ai1⋯ainAinj1∑naij(−1)ijdet(Aij) 代码实现
int dett(int a[maxn][maxn],int n)//n为阶数
{int dett0,k0,h0;if(n1) return a[0][0];else if(n2) return a[0][0]*a[1][1]-a[0][1]*a[1][0];else{for(int p0;pn;p){for(int i0;in;i)for(int j0;jn;j){if(jp) continue;tmp[h][k]a[i][j],k;if(kn-1) h,k0;}dettdetta[0][p]*pow(-1,p)*det(tmp,n-1)}return dett;}
}高斯消元
前置芝士
三角矩阵
上三角矩阵的对角线左下方的系数全部为 0 0 0下三角矩阵的对角线右上方的系数全部为 0 0 0。三角矩阵可以看作是一般方阵的一种简化情形。由于带三角矩阵的矩阵方程容易求解在解多元线性方程组时总是将其系数矩阵通过初等变换化为三角矩阵来求解。
举个栗子下面的矩阵 U U U 就是一个上三角矩阵。 U [ u 1 , 1 u 1 , 2 u 1 , 3 ⋯ u 1 , n 0 u 2 , 2 u 2 , 3 ⋯ u 2 , n 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ 0 ⋱ u n − 1 , n 0 0 ⋯ 0 u n , n ] U \begin{bmatrix} u_{1,1}u_{1,2}u_{1,3}\cdotsu_{1,n}\\ 0u_{2,2}u_{2,3}\cdotsu_{2,n}\\ 00\ddots\ddots\vdots\\ \vdots\vdots0\ddotsu_{n-1,n}\\ 00\cdots0u_{n,n} \end{bmatrix} U u1,100⋮0u1,2u2,20⋮0u1,3u2,3⋱0⋯⋯⋯⋱⋱0u1,nu2,n⋮un−1,nun,n
增广矩阵
又称扩增矩阵就是在系数矩阵的右边添上一列这一列是线性方程组的等号右边的值。
高斯消元
基本思想
通过一系列的加减消元运算将方程组化为上三角矩阵。然后再逐一回代求出 x x x。
实现过程
解方程 { 3 x 1 2 x 2 x 3 6 2 x 1 2 x 2 2 x 3 4 4 x 1 − 2 x 2 − 2 x 3 2 \begin{cases} 3x_12x_2x_36\\ 2x_12x_22x_34\\ 4x_1-2x_2-2x_32 \end{cases} ⎩ ⎨ ⎧3x12x2x362x12x22x344x1−2x2−2x32 我们把这个方程组写成增广矩阵的形式
