本文共 2757 字，大约阅读时间需要 9 分钟。

解决的问题是1给一堆数可不可以异或出某个数$x$，2这堆数的最大异或和。

构造： 对于$A$中每新增加的一个数，都从他的最高位开始遍历$P$，若$P_i\ne 0$，则$v=v\otimes P_i$，继续一直找到不为0的$P_i$，令$P_i=v$。

void ins(LL v){
   	for(int i=51;i>=0;--i){
   		if(v&(1ll<

找某个数与$A$最大异或和：

LL jmax(LL base=0){
   	LL ans=base;	for(int i=51;i>=0;--i){
   		ans=max(ans,ans^s[i]);	}	return ans;}

查询某个数是否能被表示：

线性基合并

JI merge_ji(const JI &x, const JI &y){
       JI res;    for(int i = 60; i >= 0; --i){
           if(x.a[i])res.add(x.a[i]);        if(y.a[i])res.add(y.a[i]);    }    return res;}

应用

求一个无向图中点1到点n的最大异或和路径

1. 路径是由一条主路径和一些简单环构成。因为异或会把主路径连接到环的边弄没。
2. 不同DFS序找到的简单环虽然不同，但是简单环之间异或可以得到所有图上有的简单环，所以返祖找所有环就可以了。即以下两种DFS方式虽然得到两个环不同，但都可以通过异或得到第三个环。
   

#include
   
    using namespace std;const int maxn=5e4+5,maxm=1e5+5;typedef long long LL;typedef struct{
   	int next,to;	LL v;} ooo;ooo e[maxm<<1];int head[maxn];LL to[maxn];bool vis[maxn];void addEdge(int u,int v,LL d){
   	static int cnt=0;	e[cnt]=ooo{
   head[u],v,d};	head[u]=cnt++;	e[cnt]=ooo{
   head[v],u,d};	head[v]=cnt++;}class Ji{
   	LL num[66];public:	void ins(LL v){
   		for(int i=63;i>=0;--i)			if(v&(1ll<
    
     =0;--i)			ans=max(ans,ans^num[i]);		return ans;	}}ji;void dfs(int u,LL res){
     // 返祖找出所有的简单环	to[u]=res;	vis[u]=true;	for(int i=head[u];~i;i=e[i].next){
   		if(!vis[e[i].to])dfs(e[i].to,res^e[i].v);		else ji.ins(res^e[i].v^to[e[i].to]);	}}int main(){
   	int n,m;	scanf("%d%d",&n,&m);	memset(head,-1,sizeof(head));	int u,v;	LL d;	for(int i=0;i
    
   

$$\sum _{i=1}^{n-m+1}\left[\left(a_i,a_{i+1},\cdots ,a_{i+m-1}\right)\text{ matches }b\right]\cdot 2^{i-1}\mathrm{m}\mathrm{o}\mathrm{d}\left(10^9+7\right)$$

#include
   
    #define debug(_x) cout<<#_x<<": "<<_x<
    
     >= 1;    }    return ans;}class Ji{
   	ll num[32];public:    Ji(){
           memset(num, 0, sizeof num);    }	void ins(ll v){
      // 添加到线形基中		for(int i=30;i>=0;--i)			if(v&(1<
     
      =0;--i){
               if(num[i] && v&(1<
      
       =0;--i)			if(v&(1ll<
       
        =0;--i)			ans=max(ans,ans^num[i]);		return ans;	}};int a[maxn],b[maxn],nex[maxn];int n,m,k,ans;void getNex(){
       int i=0, j=nex[0]=-1;    while(i
        
         >T; while(T--){ Ji ji; ans = 0; cin>>n>>m>>k; for(int i=0;i
         
          >a[i]; for(int i=0;i
          
           >b[i]; for(int v,i=0;i
           
            >v; ji.ins(v); } for(int i=0;i
           
          
         
        
       
      
     
    
   

转载地址：http://agkzi.baihongyu.com/