这里确实是用到了2115的一些思想,那题做法:http://blog.sina.com.cn/s/blog_6e63f59e0101bklw.html那道题求的是xor最大值,显然全部搞出来再高斯消元一下,枚举一遍就可以了。但是这道题求的是xor的种数,而且还删边,瞬间就傻掉了。首先转化一下,由于删边很难搞,就搞成加边。询问从后往前枚举,每次加一条边,这样的话比较容易判断,加进去是环边或者树边来更新。由2115得到启发,xor值是由链和环两部分构成的。于是和那道题一样,把环都搞到高斯消元的东西里面消成基数,链则另外存。两条链等价的条件就是它们用那些基数消出来的值一样。(大略想一想好像是这样但是具体的真心不太想得清楚囧)然后可以用一个set来维护这些值。如果当前基数表里面有A个元素,本质不同的链有B条,那么答案就是B * (1<< A) - 1,因为0是不能算进答案的。在加边的时候,如果判断加的这条边是树的边,那么dfs扩展当前的图;如果加边后形成了一个环,那么把环的xor值搞出来(具体和2115一样),再扔进高斯消元的里面消成基数。关于“扔进去再消”,之前做过bzoj3105,我是扔进去再全部消的,这样可以保证基数表是递减的(在消其他东西的时候只要按顺序枚举过去就可以了);这次orz了标程发现可以不用扔一次全部消一次,只要把当前的w用当前的基数表消了以后记录一些东西,这样消其他东西的时候稍微麻烦一点,要两重循环,但是不需要每次扔一个进去全部消一次(具体我也没测试过,估计了一下速度应该是差不多的吧,这样看起来比较高贵)。然后具体怎么高斯消元以及set的一些小细节可以参考程序。#include<cstdio>
#include<cstring>
#include<set>
#include<iostream>
using namespace std;
#define LL longlong
#define N5050
#define M20200
struct edge{int y,next;LL w;}e[M <<1];
int can[M],dis[M],first[N],b[70],hei[70],vis[N];
int cnt,tot,n,m,q;
LL sum[N],ans[M],a[70],tmp[M];
set <LL> S;
void addedge(int x,int y,LL z){
e[cnt].next = first[x];e[cnt].y = y;e[cnt].w = z;first[x] = cnt ++;
e[cnt].next = first[y];e[cnt].y = x;e[cnt].w = z;first[y] = cnt ++;
}
LL gauss(LL w){
for (int i = 62;i >= 0;i --)if (b[i] &&((w >>i) & 1))
for (int j = 1;j <= tot;j ++) if (hei[j] == i) w ^= a[j];
return w;
}
void loop(LL w){
if (tot == 63) return;
w = gauss(w);
if (w == 0) return;
a[++ tot] = w;
int top,k = 0;
for (top = 62;!((w >>top) & 1);top --);
hei[tot] = top;
b[top] = 1;
set <LL> :: iterator j;
LL x;
for (j = S.begin();j != S.end();){
x= *j;
if ((x >>top) & 1){
![bzoj2322-梦想封印xor高斯消元 bzoj大视野](http://img.413yy.cn/images/30101030/30062231t011e4cbe8bd9b2876a.jpg)
tmp[++k] = x ^ w;
S.erase(j);
j= S.lower_bound(x);
}else j ++;
}
for(;k;k --) S.insert(tmp[k]);
}
void dfs(int x,int fa){
vis[x] = 1;
LL w = gauss(sum[x]);
S.insert(w);
int y;
for (int i = first[x];i != -1;i = e[i].next) if (!can[i / 2] &&e[i].y != fa){
y= e[i].y;
if (!vis[y]) sum[y] = sum[x] ^ e[i].w,dfs(y,x);
else loop(sum[y] ^ sum[x] ^ e[i].w);
}
}
int main(){
scanf("%d%d%d",&n,&m,&q);
int x,y;
LL z;
memset(first,-1,sizeof first);
for (int i = 0;i < m;i ++){
scanf("%d%d%lld",&x,&y,&z);
addedge(x,y,z);
}
for (int i = 1;i <= q;i ++) scanf("%d",&dis[i]),can[--dis[i]] = 1;
dfs(1,0);
ans[q + 1] = (1LL <<tot) * S.size() - 1;
for (int i = q;i;i --){
y= e[2 * dis[i]].y,x = e[2 * dis[i] + 1].y;
can[dis[i]] = 0;
if (vis[x] + vis[y] == 2) loop(sum[y] ^ sum[x] ^ e[2 * dis[i]].w);
else if (vis[x] &&!vis[y]) sum[y] = sum[x] ^ e[2 * dis[i]].w,dfs(y,x);
else if (!vis[x] &&vis[y]) sum[x] = sum[y] ^ e[2 * dis[i]].w,dfs(x,y);
ans[i] = (1LL <<tot) * S.size() - 1;
}
for (int i = 1;i <= q + 1;i ++) printf("%lldn",ans[i]);
return 0;
}