@KirinBill
2018-02-28T07:43:37.000000Z
字数 18443
阅读 1661
线性代数
目录
向量空间是线性代数研究的基本对象,可以简单的认为是在高中就是直角坐标系里的所有向量组成的集合。其实我们可以很多其它集合也看做向量,同时定义一下向量加法和标量乘法,就可以通过基向量的运算来表示出其它所有向量,这也是一个向量空间了。
定义为向量空间,其中为域(中元素的范围,大概类似于定义域),为集合,中的元素称为向量,为向量加法,为标量乘法。并且要求运算满足条公理(见维基百科)。
对于向量空间中的一个向量组,若存在不全为的一组数,使得,则称这个向量组线性相关,否则称为线性无关。
线性相关有些地方就类似与高中数学的两个向量共线。
对于向量空间中的一个向量组,一组数,和一个新向量,称是向量组的一个线性组合,而且必然有。
之所以叫线性组合,是因为如果将这个向量空间以直角坐标系的形式呈现,那么向量仍是直的,也就是说线性组合的运算不会弯曲向量。
性质:一组向量线性无关其中不存在一个向量是该组的其它向量的一个线性组合
对于向量空间中的一个向量组,其所有线性组合构成的集合称为其张成,记做。
例子:高中数学中,平面的一个向量基底,其张成就是整个平面的所有向量,其张成空间就是整个平面,因为平面上的所有向量都可以用它们的线性组合表示(即写成的形式)。
若向量空间中的一个向量组即可张成出,又是线性无关的,则称其为的一个基,为该向量空间的维数。
性质:
- 是能张成的极小集合,其任何真子集都不能张成出;
- 是该向量空间中线性无关的极大集合,该向量空间中不存在其它线性无关的向量集合使是其真子集;
- 中的每一个向量都可以用中的一个唯一的线性组合表示。
第三点感性的证明就是如果存在不唯一的方案,那么一定说明中有一个向量可以通过其它向量的线性组合表示,与定义矛盾。
总之,基向量就类似于高中数学用的基底,我们可以用它来代表一个向量空间,从而“减小”向量空间的大小。
从Sengxian巨佬那里偷来的例子:
。
一开始矩阵是这样的:
代码:
class LinearB{
private:
long long c[MAXDIM];
void ist(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
break;
}
}
}
public:
void init(long long a[],int n){
for(int i=1;i<=n;++i)
ist(a[i]);
}
};
代码:
#include <cstdio>
const int MAXN=55,MAXDIM=55;
long long a[MAXN];
class LinearB{
private:
long long c[MAXDIM];
void ist(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
break;
}
}
}
public:
void init(long long a[],int n){
for(int i=1;i<=n;++i)
ist(a[i]);
}
long long qry_max(){
long long ret=0;
for(int i=0;i<MAXDIM;++i)
ret^=c[i];
return ret;
}
}lb;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
lb.init(a,n);
printf("%lld",lb.qry_max());
return 0;
}
代码:
#include <cstdio>
#include <algorithm>
#include <vector>
using std::sort;
using std::vector;
const int MAXN=1e5+5,MAXDIM=55;
long long a[MAXN];
class LinearB{
private:
long long span_sz;
bool has_zero;
long long c[MAXDIM];
vector<long long> vec;
void ist(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
break;
}
}
}
public:
void init(long long a[],int n){
for(int i=1;i<=n;++i)
ist(a[i]);
for(int i=0;i<MAXDIM;++i){
if(c[i]) vec.push_back(c[i]);
}
// long long !!!
span_sz=(1LL<<vec.size())-1;
if(n>vec.size()) has_zero=true;
sort(vec.begin(),vec.end());
}
long long kth_val(long long k){
if(has_zero) --k;
if(k>span_sz) return -1;
long long ret=0;
for(int i=0;i<vec.size();++i){
if(k>>i&1) ret^=vec[i];
}
return ret;
}
}lb;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
lb.init(a,n);
int m;
scanf("%d",&m);
long long k;
for(int i=1;i<=m;++i){
scanf("%lld",&k);
printf("%lld\n",lb.kth_val(k));
}
return 0;
}
代码:
#include <cstdio>
const int MAXN=100005,MAXDIM=32;
int n;
int a[MAXN];
class LinearB{
private:
int c[MAXDIM];
void ist(int x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
break;
}
}
}
public:
void init(int a[],int n){
for(int i=1;i<=n;++i)
ist(a[i]);
}
int qry_max(){
int ret=0;
for(int i=0;i<MAXDIM;++i)
ret^=c[i];
return ret;
}
int lb_min(){
for(int i=0;i<MAXDIM;++i){
if(c[i]) return c[i];
}
}
}lb;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
lb.init(a,n);
int max=lb.qry_max();
printf("%d %d",max,max^lb.lb_min());
return 0;
}
代码:
#include <cstdio>
#include <algorithm>
using std::sort;
const int MAXN=1005,MAXDIM=60;
int n;
struct data{
int val;
long long id;
static bool cmp_val(const data &a,const data &b){
return a.val>b.val;
}
}w[MAXN];
class LinearB{
private:
long long c[MAXDIM];
public:
bool ist(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
return true;
}
}
return false;
}
};
inline int greedy(){
static LinearB lb;
sort(w+1,w+n+1,data::cmp_val);
int ret=0;
for(int i=1;i<=n;++i){
if(lb.ist(w[i].id))
ret+=w[i].val;
}
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld%d",&w[i].id,&w[i].val);
printf("%d",greedy());
return 0;
}
代码:
#include <cstdio>
#include <vector>
using std::vector;
const int MAXN=50005,MAXM=100005,MAXDIM=60;
int he[MAXN];
long long dis[MAXN];
vector<long long> cir;
struct line{
int to,nex;
long long w;
}ed[MAXM<<1];
class LinearB{
private:
long long c[MAXDIM];
void ist(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
break;
}
}
}
public:
void init(vector<long long> &a){
for(int i=0;i<a.size();++i)
ist(a[i]);
}
long long qry_max(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) x^=c[i];
}
return x;
}
}lb;
inline void addE(int u,int v,long long w){
static int cnt;
ed[++cnt]=(line){v,he[u],w};
he[u]=cnt;
}
void DFS(int u,int fa){
static bool vis[MAXN];
vis[u]=true;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v==fa) continue;
if(!vis[v]){
dis[v]=dis[u]^ed[i].w;
DFS(v,u);
}
else cir.push_back(dis[u]^dis[v]^ed[i].w);
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
long long w;
for(int i=1,u,v;i<=m;++i){
scanf("%d%d%lld",&u,&v,&w);
addE(u,v,w),addE(v,u,w);
}
DFS(1,0);
lb.init(cir);
printf("%lld",lb.qry_max(dis[n]));
return 0;
}
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using std::swap;
const int MAXN=20005,MAXDIM=61,MAXLOG=15;
int n;
int he[MAXN],de[MAXN],anc[MAXN][MAXLOG];
long long w[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
class LinearB{
public:
long long c[MAXDIM];
void ist(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
break;
}
}
}
LinearB(){memset(c,0,sizeof(c));}
LinearB& operator +=(const LinearB &that){
for(int i=0;i<MAXDIM;++i){
if(that.c[i]) ist(that.c[i]);
}
return *this;
}
LinearB operator +(const LinearB &that)const{
LinearB ret=*this;
ret+=that;
return ret;
}
long long qry_max(){
long long ret=0;
for(int i=0;i<MAXDIM;++i)
ret^=c[i];
return ret;
}
}lb[MAXN][MAXLOG];
inline void addE(int u,int v){
static int cnt;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
void DFS(int u){
de[u]=de[anc[u][0]]+1;
lb[u][0].ist(w[u]);
lb[u][0].ist(w[anc[u][0]]);
for(int i=1,lim=log2(de[u]);i<=lim;++i){
anc[u][i]=anc[anc[u][i-1]][i-1];
lb[u][i]=lb[u][i-1]+lb[anc[u][i-1]][i-1];
}
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=anc[u][0]){
anc[v][0]=u;
DFS(v);
}
}
}
inline long long dbl_jump(int u,int v){
if(u==v) return w[u];
if(de[u]<de[v]) swap(u,v);
LinearB ret;
for(int d=de[u]-de[v],i=0;d;++i,d>>=1){
if(d&1){
ret+=lb[u][i];
u=anc[u][i];
}
}
if(u==v) return ret.qry_max();
for(int i=MAXLOG-1;i>=0;--i){
if(anc[u][i]!=anc[v][i]){
ret+=lb[u][i]+lb[v][i];
u=anc[u][i],v=anc[v][i];
}
}
ret+=lb[u][0]+lb[v][0];
return ret.qry_max();
}
int main(){
int q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)
scanf("%lld",&w[i]);
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
addE(u,v),addE(v,u);
}
DFS(1);
for(int i=1,u,v;i<=q;++i){
scanf("%d%d",&u,&v);
printf("%lld\n",dbl_jump(u,v));
}
return 0;
}
std::set
里就可以了对链去重了;std::set
,而且只会删,因为线性基里只会增加元素。而线性基里每增加一个元素,属性值在这一位就只能是,属性值的种类也就减半,所以暴力更新就可以了。代码:
#include <cstdio>
#include <set>
using std::set;
const int MAXN=5005,MAXM=20005,MAXQ=MAXM,MAXDIM=60;
int he[MAXN],del_id[MAXQ];
long long dis[MAXN],ans[MAXQ];
bool vis[MAXN],del[MAXM];
set<long long> se;
struct graph{
int u,v;
long long w;
}G[MAXM];
struct line{
int to,nex;
long long w;
}ed[MAXM<<1];
class LinearB{
private:
int sz;
long long c[MAXDIM];
void upd_attrib(){
static long long tmp[MAXN];
tmp[0]=0;
for(set<long long>::iterator iter=se.begin();iter!=se.end();++iter)
tmp[++tmp[0]]=*iter;
se.clear();
for(int i=1;i<=tmp[0];++i)
se.insert(attrib(tmp[i]));
}
public:
void ist(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
++sz;
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
upd_attrib();
break;
}
}
}
long long attrib(long long x){
for(int i=MAXDIM-1;i>=0;--i){
if(x>>i&1) x^=c[i];
}
return x;
}
int size(){return sz;}
}lb;
inline void addE(int u,int v,long long w){
static int cnt;
ed[++cnt]=(line){v,he[u],w};
he[u]=cnt;
}
void DFS(int u,int fa,long long dis){
vis[u]=true;
::dis[u]=dis;
se.insert(lb.attrib(dis));
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v==fa) continue;
if(!vis[v]) DFS(v,u,dis^ed[i].w);
else lb.ist(::dis[u]^::dis[v]^ed[i].w);
}
}
inline void addE(graph &e){
if(vis[e.u] && vis[e.v])
lb.ist(dis[e.u]^dis[e.v]^e.w);
else{
addE(e.u,e.v,e.w),addE(e.v,e.u,e.w);
if(vis[e.u]) DFS(e.v,e.u,dis[e.u]^e.w);
else if(vis[e.v]) DFS(e.u,e.v,dis[e.v]^e.w);
}
}
inline long long cal(){return se.size()*(1LL<<lb.size())-1;}
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;++i)
scanf("%d%d%lld",&G[i].u,&G[i].v,&G[i].w);
for(int i=1;i<=q;++i){
scanf("%d",&del_id[i]);
del[del_id[i]]=true;
}
for(int i=1;i<=m;++i){
if(!del[i]) addE(G[i]);
}
DFS(1,0,0);
ans[++q]=cal();
for(int i=q-1;i;--i){
addE(G[del_id[i]]);
ans[i]=cal();
}
for(int i=1;i<=q;++i)
printf("%lld\n",ans[i]);
return 0;
}
代码:
#include <cstdio>
#include <vector>
using std::vector;
const int MAXN=100005,MAXDIM=31,P=10086;
int a[MAXN];
class LinearB{
private:
int c[MAXDIM];
vector<int> vec;
void ist(int x){
for(int i=MAXDIM-1;i>=0;--i){
if(~x>>i&1) continue;
if(c[i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i]>>j&1) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j]>>i&1) c[j]^=c[i];
}
break;
}
}
}
public:
int size(){return vec.size();}
void init(int a[],int n){
for(int i=1;i<=n;++i)
ist(a[i]);
for(int i=0;i<MAXDIM;++i){
if(c[i]) vec.push_back(i);
}
}
int get_rk(int x){
int ret=0;
for(int i=0;i<vec.size();++i){
if(x>>vec[i]&1) ret+=1<<i;
}
++ret; //线性基全不选的情况
return ret;
}
}lb;
int pow(int x,int y){
int ret=1;
for(;y;x=(long long)x*x%P,y>>=1){
if(y&1) ret=(long long)ret*x%P;
}
return ret;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
lb.init(a,n);
int q;
scanf("%d",&q);
printf("%d",((long long)(lb.get_rk(q)%P-1+P)%P*pow(2,n-lb.size())%P+1)%P);
return 0;
}
unsigned long long
也会溢出,我们应该存成的形式;代码:
#include <cstdio>
#include <vector>
using std::vector;
const int MAXN=100005;
int n,K;
unsigned long long a[MAXN];
inline void solve1(){
unsigned long long ret=0;
for(int i=1;i<=n;++i)
ret|=a[i];
printf("%llu",ret>>1);
if(ret&1) printf(".5");
}
inline void solve2(){
int tmp=0;
unsigned long long ret=0;
bool flag;
for(int i=0;i<32;++i){
flag=false;
for(int j=1;j<=n;++j){
if(a[j]>>i&1){
flag=true;
break;
}
}
if(!flag) continue;
for(int j=0;j<32;++j){
flag=false;
for(int k=1;k<=n;++k){
if(a[k]>>j&1){
flag=true;
break;
}
}
if(!flag) continue;
flag=false;
for(int k=1;k<=n;++k){
if((a[k]>>i&1)!=(a[k]>>j&1)){
flag=true;
break;
}
}
//tmp是目前除不了的贡献,记到一起最后除
//单位是1/2,对于i=j=0时才可能为-2,但此时flag比为false,不存在,所以这里只有÷2的情况
if(i+j-1-flag<0) ++tmp;
else ret+=1LL<<i+j-1-flag; //除过了(左移位数-1-flag)
}
}
ret+=tmp>>1;
printf("%llu",ret);
if(tmp&1) printf(".5");
}
inline void solve3(){
static int lb[22];
static vector<int> vec;
for(int i=1;i<=n;++i){
for(int j=21;j>=0;--j){
if(~a[i]>>j&1) continue;
if(lb[j]) a[i]^=lb[j];
else{
lb[j]=a[i];
for(int k=j-1;k>=0;--k){
if(lb[j]>>k&1) lb[j]^=lb[k];
}
for(int k=j+1;k<22;++k){
if(lb[k]>>j&1) lb[k]^=lb[j];
}
break;
}
}
}
for(int i=0;i<22;++i){
if(lb[i]) vec.push_back(lb[i]);
}
long long ret1=0,ret2=0,tmp1,tmp2;
for(int i=0,tmp,lim=1<<vec.size();i<lim;++i){
tmp=0;
for(int j=0;j<vec.size();++j){
if(i>>j&1) tmp^=vec[j];
}
tmp1=0,tmp2=1;
for(int j=1;j<=K;++j){
tmp1*=tmp,tmp2*=tmp;
tmp1+=tmp2>>vec.size();
tmp2&=lim-1;
}
ret1+=tmp1,ret2+=tmp2;
ret1+=ret2>>vec.size();
ret2&=lim-1;
}
printf("%lld",ret1);
if(ret2) printf(".5");
}
int main(){
scanf("%d%d",&n,&K);
for(int i=1;i<=n;++i)
scanf("%llu",&a[i]);
if(K==1) solve1();
else if(K==2) solve2();
else solve3();
return 0;
}
std::bitset
存,有点毒瘤。代码:
#include <iostream>
#include <bitset>
#include <algorithm>
#include <vector>
using std::cin;
using std::cout;
using std::ios;
using std::bitset;
using std::swap;
using std::vector;
const int MAXN=505,MAXM=505,MAXP=1005,MAXBIT=1005,MAXDIM=MAXBIT;
int n,m,p;
int he[MAXN],opt_st[MAXP];
bitset<MAXBIT> dis[MAXN],ans[MAXP];
struct graph{
int u,v;
bitset<MAXBIT> w;
}G[MAXM],opt[MAXP];
vector<graph> nTreeE;
struct line{
int to,nex;
bitset<MAXBIT> w;
}ed[MAXN<<1];
class UFS{
private:
int fa[MAXN],dist[MAXN];
public:
void init(int n){
for(int i=1;i<=n;++i)
fa[i]=i,dist[i]=1;
}
int find(int x){
if(x==fa[x]) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void uni(int x,int y){
if(dist[x]<dist[y]) swap(dist[x],dist[y]);
fa[y]=x,dist[x]+=(dist[y]==dist[x]);
}
};
class LinearB{
private:
bitset<MAXBIT> c[MAXDIM];
public:
void ist(bitset<MAXBIT> &x){
for(int i=MAXDIM-1;i>=0;--i){
if(x[i]==0) continue;
if(c[i][i]) x^=c[i];
else{
c[i]=x;
for(int j=i-1;j>=0;--j){
if(c[i][j]) c[i]^=c[j];
}
for(int j=i+1;j<MAXDIM;++j){
if(c[j][i]) c[j]^=c[i];
}
break;
}
}
}
bitset<MAXBIT> qry_max(){
bitset<MAXBIT> ret;
for(int i=0;i<MAXDIM;++i)
ret^=c[i];
return ret;
}
};
class segT{
#define ls (u<<1)
#define rs (ls|1)
private:
vector<bitset<MAXBIT> > vec[MAXP<<2];
void ist(int u,int l,int r,int lp,int rp,bitset<MAXBIT> &x){
if(lp<=l && r<=rp){
vec[u].push_back(x);
return;
}
int mid=l+r>>1;
if(lp<=mid) ist(ls,l,mid,lp,rp,x);
if(rp>mid) ist(rs,mid+1,r,lp,rp,x);
}
void DC(int u,int l,int r,LinearB lb,bitset<MAXBIT> ans[]){
for(int i=0;i<vec[u].size();++i)
lb.ist(vec[u][i]);
if(l==r){
ans[l]=lb.qry_max();
return;
}
int mid=l+r>>1;
DC(ls,l,mid,lb,ans);
DC(rs,mid+1,r,lb,ans);
}
public:
void ist(int l,int r,bitset<MAXBIT> x){ist(1,0,p,l,r,x);}
void DC(bitset<MAXBIT> ans[]){
LinearB lb;
DC(1,0,p,lb,ans);
}
#undef ls
#undef rs
}T;
inline void out_bitset(bitset<MAXBIT> &x){
int cur;
for(cur=MAXBIT-1;cur;--cur){
if(x[cur]) break;
}
for(;cur>=0;--cur) cout<<x[cur];
}
inline void addE(int u,int v,bitset<MAXBIT> &w){
static int cnt;
ed[++cnt]=(line){v,he[u],w};
he[u]=cnt;
}
inline void spanT(){
static UFS ufs;
ufs.init(n);
for(int i=1,u,v,ufa,vfa;i<=m;++i){
u=G[i].u,v=G[i].v;
ufa=ufs.find(u),vfa=ufs.find(v);
if(ufa!=vfa){
ufs.uni(ufa,vfa);
addE(u,v,G[i].w),addE(v,u,G[i].w);
}
else nTreeE.push_back(G[i]);
}
}
void DFS(int u,int fa){
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa){
dis[v]=dis[u]^ed[i].w;
DFS(v,u);
}
}
}
inline void fast_ios(){
ios::sync_with_stdio(false);
cin.tie(NULL);
}
int main(){
fast_ios();
cin>>n>>m>>p;
for(int i=1;i<=m;++i)
cin>>G[i].u>>G[i].v>>G[i].w;
spanT();
DFS(1,0);
for(int i=0;i<nTreeE.size();++i)
T.ist(0,p,dis[nTreeE[i].u]^dis[nTreeE[i].v]^nTreeE[i].w);
int k=0;
char cmd[10];
for(int i=1,x;i<=p;++i){
cin>>cmd;
//add
if(cmd[1]=='d'){
opt_st[++k]=i;
cin>>opt[k].u>>opt[k].v>>opt[k].w;
}
//cancel
else if(cmd[1]=='a'){
cin>>x;
T.ist(opt_st[x],i-1,dis[opt[x].u]^dis[opt[x].v]^opt[x].w);
opt_st[x]=0;
}
else{
cin>>x;
T.ist(opt_st[x],i-1,dis[opt[x].u]^dis[opt[x].v]^opt[x].w);
cin>>opt[x].w;
opt_st[x]=i;
}
}
for(int i=1;i<=k;++i){
if(opt_st[i]) T.ist(opt_st[i],p,dis[opt[i].u]^dis[opt[i].v]^opt[i].w);
}
T.DC(ans);
for(int i=0;i<=p;++i){
out_bitset(ans[i]);
cout<<'\n';
}
return 0;
}