找网络公司做网站需要注意,网站做互动,深圳大鹏住房和建设局网站,网站建设与维护笔记向量空间 向量空间亦称线性空间。 形式化的#xff0c;我们定义一个向量空间\((P,V,,\cdot)\) 其中 \(P\)是一个域#xff0c;\(V\)是一个非空的集合#xff0c;其中的集合称作向量#xff0c;同时定义两种运算分别为向量加法和标量乘法 一个\(P\)上的向量空间\((P,V,,\cdo… 向量空间 向量空间亦称线性空间。 形式化的我们定义一个向量空间\((P,V,,\cdot)\) 其中 \(P\)是一个域\(V\)是一个非空的集合其中的集合称作向量同时定义两种运算分别为向量加法和标量乘法 一个\(P\)上的向量空间\((P,V,,\cdot)\)需满足以下8条公理其中的\(u,v,w\in V\),\(a,b\)是标量 \(u(vw)(uv)w\)\(uvvu\)\(\exists\mathbf{0}\)\(s.t. \ \ v\mathbf{0}v\)\(\forall v\in V,\exists w\in V\)\(s.t.\) \(v w 0\)\(a(uv)auav\)\((ab)vavbv\)\(a(bv)(ab) v\)\(\exists 1,s.t. \ 1 \cdot vv\) 基basis 向量空间\(V\)的基是可以张成\(V\)的一个线性无关的向量组其中的元素称作基向量。 异或运算线性基 把一个数的二进制表示看成是一个向量\[ \mathbf{a}_i(d_n,...d_0) \] 假设向量\(\mathbf{a}_0,\mathbf{a}_1,...\mathbf{a}_m\)的张成空间是\(S\) 定义一个向量空间\(V(\{ 0,1\} ,S,xor,\cdot)\) \(ps:\)这里我们是把异或当作加法 求法 如何求出\(V\)的一个基\(\mathfrak{B}\) 我们要做的是扫描每一个向量\(\mathbf{a}_i\)如果它存在于其它向量的张成空间中就把它去掉 如何判断每个向量能否被前面的向量张成得到 我们利用高斯消元: int a[MN],base[log_MN];
inline void calc()
{//n is the highest bitregister int i,j,k;for(i0;im;i)for(jn;~j;--j)if(a[i]j1)//Scan every bit of a[I] from top to bottom{if(base[j]) a[i]^base[j];else{//Theres no vector for this bitbase[j]a[i];/*Maintain a diagonal matrixfor(kj-1;~k;--k) if(base[k](base[j]k1)) base[j]^base[k];for(kj1;kn;k) if(base[k]j1) base[k]^base[j];*/break;}}
} 复杂度是\(O(mn)\)若位数较多通常采用bitset优化复杂度是\(O(\frac{mn^2}{\omega})\) 可以发现我们在维护一组向量\(base[]\)满足\(base_i\)的最高位时\(i\) 为了方便通常只把它消成一个上三角矩阵 当然你也可以把它消成一个类对角线矩阵满足每一位最多只存在于一个向量中 线性基的运用 在这里我们不严谨地称一个向量另一个向量 其实指的是每个向量对应的数的大小比较 查询最值 贪心求最大值 如果所求是类对角线矩阵直接将所有向量相加即可如果所求的是上三角矩阵从高到低遍历每个向量若ans加上当前的向量会变大就将其贪心的加上 最小值是线性基中最小的向量 查询第k小值 首先在去重的前提下。 首先我们求出类对角线矩阵 那么如果 \(k(100101)_2\)我们所求的即为\(base_0 base_2base_5\) 也就是各位所对应的数Xor起来即可 查询和是第几大 如果在去重的前提下和查询第k小差不多。 如果不在去重的前提下的话 设\(m\)为给出数的个数 \(\mathfrak{B}\)为所求线性基 结论每个数都出现一样的次数且这个次数为 \(2^{m - \vert \mathfrak{B}\vert}\) 证明 所有不在线性基中的数的个数为 \(m - \vert \mathfrak{B}\vert\)我们任意选择它的一个子集 \(S\)对于 \(S\) 中的每个数 \(v\)有唯一的方式表达为 \(\mathfrak {B}\)中向量的线性组合。我们对于每个 \(v\)将这个线性组合中的向量都选上一个向量选多次可以看作是次数对\(2\)取模后的结果两个相同的数异或起来得到 \(0\)所以对于每个数 \(x\)我们都能找到至少\(2^{n - \vert \mathfrak{B}\vert}\) 种不同的选择方案使得异或值为 \(x\)。又因为对于每个子集 \(S\)为了使得最终异或值为 \(x\)选择线性基中的向量的方案是唯一的所以上界也是 \(2^{n - \vert \mathfrak{B}\vert}\)。 此结论同时出现在2019/2/24 福建四校联考中的T1 总结 观察大佬博客Sengxianblog后...... 线性基的题型相对比较固定看到下面的类型基本上都是线性基了 最大异或和 例题luogu模板题第 \(k\)大异或和/异或和是第几大 例题bzoj 2844求所有异或值的和 例题bzoj 3811线性基中的题目中还用到一个技巧 任意一条\(1\) 到 \(n\) 的路径的异或和都可以由任意一条 \(1\)到 \(n\) 路径的异或和与图中的一些环的异或和来组合得到。例题bzoj 2115这便是线性基的全部东西了。 Code 洛谷P3812 #includebits/stdc.h
#define ll long long
using namespace std;
inline ll read()
{ll x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){x(x3)(x1)ch-0;chgetchar();}return x*f;
}
#define MN 55
ll n,base[MN],ans;
inline void insert(ll x)
{register int i,j;for(i50;~i;--i)if(xi1){if(base[i]) x^base[i];else{base[i]x;for(ji-1;~j;--j)if(base[j](base[i]j1))base[i]^base[j]; for(ji1;j50;j)if(base[j]i1)base[j]^base[i];break;}}
}
int main()
{nread();register int i;for(i1;in;i) insert(read()); for(i0;i50;i) ans^base[i];return 0*printf(%lld\n,ans);
} bzoj 2115 Xor link dfs出所有的环 求出它们的线性基 #includebits/stdc.h
#define ll long long
#define max(a,b) ((a)(b)?(a):(b))
#define min(a,b) ((a)(b)?(a):(b))
inline ll read()
{ll x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){x(x3)(x1)ch-0;chgetchar();}return x*f;
}
const int MN200005,mN50005,_61;
ll a[MN],tp,dfn[mN],dind,Xor[mN],b[_];
struct edge{int to;ll w;int nex;}e[MN1];
int N,M,hr[mN],en;
ll ans0;
inline void ins(int x,int y,ll w)
{e[en](edge){y,w,hr[x]};hr[x]en;e[en](edge){x,w,hr[y]};hr[y]en;
}
inline void tj(int x,int f)
{register int i;dfn[x]dind;for(ihr[x];i;ie[i].nex)if(e[i].to^f){if(!dfn[e[i].to]) Xor[e[i].to]Xor[x]^e[i].w,tj(e[i].to,x);else a[tp]Xor[x]^Xor[e[i].to]^e[i].w;}
}
inline void calc()
{register int i,j,k;for(i1;itp;i)for(j_-1;~j;--j)if(a[i]j1){if(b[j]) a[i]^b[j];else{b[j]a[i];break;}}ansXor[N];for(i_-1;~i;--i) if((ans^b[i])ans) ans^b[i];
}
int main()
{Nread();Mread();int x,y;while(M--) xread(),yread(),ins(x,y,read());tj(1,0);calc();return 0*printf(%lld\n,ans);
} 2019福建四校联考T1 link~ 首先容斥一下转而求异或值为1的个数\[ans(2^n-1)(2^m-1)-num1\] 然后对于一行如果这一行的异或值不为0它总有\(2^{m-1}\)个选法使得选出的点的异或值是1易证 把每行当做一个数我们只需要求出有哪些行的异或值为0\[num12^{m-1}*(2^n-cnt0)\] 我们求出线性基根据线性基的性质异或值为0的个数一定是\(2^{n - \vert \mathfrak{B}\vert}\) /*
2019/2/26 15:21
*/
#includebits/stdc.h
#define ll long long
#define max(a,b) ((a)(b)?(a):(b))
#define min(a,b) ((a)(b)?(a):(b))
inline int read()
{int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){x(x3)(x1)ch-0;chgetchar();}return x*f;
}
const ll mod998244353,MN2005;
std::bitsetMN a[MN],base[MN];
int N,M,B;
ll ans;
inline void calc()
{register int i,j,k;for(i1;iN;i)for(jM-1;~j;--j)if(a[i][j]){if(base[j].count()) a[i]^base[j];else{base[j]a[i];break;}}for(i0;iM;i) if(base[i].count()) B;
}
inline ll fpow(ll x,int m)
{ll r1;for(;m;m1,x1ll*x*x%mod) if(m1) r1ll*r*x%mod;return r;
}
int main()
{freopen(password.in,r,stdin);freopen(password.out,w,stdout);Nread();Mread();register int i,j;for(i1;iN;i)for(j0;jM;j) a[i][j]read()1;calc();ans(1ll*(fpow(2,N)-1)*(fpow(2,M)-1)%modmod)%mod;ans-(1ll*fpow(2,M-1)*(fpow(2,N)-fpow(2,N-B)mod)%mod)%mod;ansmod,ans%mod;return 0*printf(%lld\n,ans);
} 暂时咕咕咕。 Blog来自PaperCloud未经允许请勿转载TKS 转载于:https://www.cnblogs.com/PaperCloud/p/10428084.html
