注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

XYP的博客

枫染红尘谁看透

 
 
 

日志

 
 

异或线性基  

2016-02-12 20:56:09|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先,可以发现异或值会有很多重复。
用原来的数xor出一个数组a‘,使这个数组:
1、a'中的数xor后的集合==原数组xor值的集合。
2、a'[i..n]xor后的max>a'[i+1..n]xor后的max>...>a'[n]
inline bool Gauss()
{
tot=0;
int M=62;
for (;M>=0;M--)
{
int j=tot+1;
while ((!(a[j]>>M&1))&&j<=n) j++;
if (j>n) continue;
tot++;swap(a[j],a[tot]);
for (int i=1;i<=n;i++) 
if ((a[i]>>M&1)&&(i!=tot)) a[i]^=a[tot];
}
return((tot!=n));
}
首先,由于每次找到第tot个数,都会把其他第M为1的数xor,这样其他的数的第M位就成了0.
若M从大到小来一波,就可以把1~tot的数的最高二进制位从大到小排序(第一个最高二进制位最大,第二个次之......)。
由于A xor B后不可能出现AB都为0的某一位变为1,所以可以保证性质2。

我们把M的代表设为第M次选的那个数,显然,M的代表是a‘中唯一一个M位上是1的数。

对于性质1,由于a’[1..tot]是根据a[] xor出的,所以只要从后往前用a'[i]xor一次a'[j],就可以xor出a[]在上一次变化的值。这样,a'[]就可以通过变化换原a[],性质1也是成立的。

求出a'[]有什么用呢?
第k小xor值:http://acm.hdu.edu.cn/showproblem.php?pid=3949
显然,对于xor第i位的代表a'[j],不管a'[j+1..tot]怎么变化,都不可能出现在第i位上为1的情况。而a’[j+1..tot]会产生2^(tot-j)种xor方案。于是,选择第a'[j]就使排名上升了2^(tot-j)。
对于一个K,我们通过1~tot枚举a‘[i],若K>=2^(tot-i),就把ans xor a’[i]。(类似splay询问第K大的数)。



K在xor结果的集合中的排名:http://www.lydsy.com/JudgeOnline/problem.php?id=2844
从前一题中考虑一个数是怎样形成的:把a‘从大到小依次xor过去。
这样,对于一个结果num,从大到小把a’中的数xor过去,若num^a'[j]<K,则num^a'[j+1..tot]<K(a'[j+1..tot]最高位<a'[j])
那么,我们就可以像数位DP一样把a‘[]从大到小试过去,若num^a'[i]<K,就把num^=a'[i],ans+2^(tot-j)。
然而怎么计算重复的数呢?
发现对于没有作为某一位代表的数,起必定可以被某些作为代表的数表示出来。这样,不被当作代表的数对最终xor的结果不产生影响(若被用于表示的数没选则选,否则就不选)。这样没个结果都会重复2^(n-tot)。
#include<cstdio>
#include<cstring>
#include<iostream>

#define nn 100010
#define Mod 10086
#define ll long long
using namespace std;
int Num,Mul,a[nn],tot,n,m,K;ll B[nn],Ans;
inline int read()
{
char c=getchar();int num=0;
while ('0'>c||c>'9') c=getchar();
while ('0'<=c&&c<='9') num=num*10+c-'0',c=getchar();
return(num);
}
inline void Gauss()
{
tot=0;
for (int M=31;M>=0;M--)
{
for (int j=tot+1;j<=n;j++)
if (a[j]>>M&1)
{
tot++;swap(a[tot],a[j]);
for (int j=1;j<=n;j++) 
if ((a[j]>>M&1)&&j!=tot) a[j]^=a[tot];
break;
}
}
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
n=read();
for (int i=1;i<=n;i++) a[i]=read();
Gauss(); int K=read();
B[0]=1;
for (int i=1;i<=n;i++) B[i]=(ll)B[i-1]*2%Mod;
int Num=0,ans=0;
ll Mul=B[n-tot];
for (int i=1;i<=tot;i++)
if ((Num^a[i])<=K) 
{
//printf("%d %d\n",i,Num);
Num^=a[i],Ans=(Ans+(B[tot-i])*B[n-tot]%Mod)%Mod,ans=(ans+B[tot-i])%Mod;
}
//printf("%d\n",ans);
printf("%d\n",(Ans+1)%Mod);
}



bzoj 2115:http://www.lydsy.com/JudgeOnline/problem.php?id=2115
显然,一条路线可以分为1..n的路径和一些环。
对于环,我们用dfs求出一部分环。虽然dfs并不能求出所有还,但由于被包含的环=大环xor其他在大环中的环,只要掌握了某些环的xor,就可以推出所有环的xor。于是,问题变成了:某些环xor值的数组A[]中某个xor值 ^  某条1..n的路径的xor。
对于前一个数,可以用线性基求出。
考虑1..n的路径:1)、1..n只有一条路,依次dfs即可求出。
2)、1..n有多条路,因为在无向图中,所以必定构成了环。任何一条路都可以用已知的一条路xor某些包含这条边的环来表示。
接着在用dis[n]对线性基搞一遍就好了。
#include<cstdio>
#include<cstring>
#include<iostream>

#define nn 200010
#define ll long long
using namespace std;
struct edge{int to,old;ll len;}e[nn];
ll A[nn],dis[nn];int tot,N,l[nn],n,m;bool vis[nn];
inline int read()
{
char c=getchar();int num=0;
while ('0'>c||c>'9') c=getchar();
while ('0'<=c&&c<='9') num=num*10+c-'0',c=getchar();
return(num);
}
inline void add(int x,int y,ll z) {e[++tot].to=y;e[tot].old=l[x];e[tot].len=z;l[x]=tot;}
inline void dfs(int x,ll num)
{
ll xx;
vis[x]=0;dis[x]=num;
for (int i=l[x];i;i=e[i].old)
if (vis[e[i].to]) dfs(e[i].to,num^e[i].len);
else if (xx=(num^e[i].len^dis[e[i].to])) A[++N]=xx;
}
inline void Gauss()
{
tot=0;
for (int M=62;M>=0;M--)
for (int i=tot+1;i<=N;i++)
{
if (A[i]>>M&1)
{
tot++; swap(A[i],A[tot]);
for (int j=1;j<=N;j++) if ((A[j]>>M&1)&&(j!=tot)) A[j]^=A[tot];
break;
}
}
}
int main()
{
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
n=read(),m=read();
for (int i=1;i<=m;i++)
{
int x=read(),y=read();ll z;scanf("%lld",&z);
add(x,y,z); add(y,x,z);
}
memset(vis,1,sizeof(vis));
dfs(1,0); 
Gauss();
ll Ans=dis[n];
for (int i=1;i<=tot;i++) 
if (Ans<(Ans^A[i])) Ans^=A[i];
printf("%lld\n",Ans);
}
  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018