线性基四题
|Word count:2k|Reading time:10min|Post View:
POI2003 Sequences without Stammers
题目链接
BZOJ 2606
题目描述
第一行包含两个整数$N$和$M$，表示该无向图中点的数目与边的数目。 接下来$M$行描述$M$条边，每行三个整数$S_i,T_i,D_i$，表示$S_i$与$T_i$之间存在一条权值为 $D_i$的无向边。 图中可能有重边或自环。
仅包含一个整数，表示最大的$XOR$和（十进制结果），注意输出后加换行回车。
题解
裸线性基，曾经在CF上做过这题，大致思路就是将所有能遍历到的环插入线性基内，因为一定能通过经过一条路径绕环一圈再从这个路径回来的方式，使得答案异或上环的权值，那么任取一条$1$到$n$的路径到线性基中求异或最大值即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+1;
struct XOR{
ll a[63];
void add(ll x){
for(int i=62;i>=0;--i)
if((x>>i)&1)x^=a[i];
for(int i=62;i>=0;--i)
if(((x>>i)&1)&&!a[i]){
a[i]=x;
for(int j=i+1;j<=62;++j)
if((a[j]>>i)&1)a[j]^=x;
return;
}
}
ll sum(ll x){
for(int i=62;i>=0;--i)
if(((x>>i)&1)==0)x^=a[i];
return x;
}
}T;
int head[N],n,m;
bool vis[N];
ll d[N];
struct nd{
int ne,to;ll w;
}e[N*2];
void in(int x,int y,ll w){
static int cnt=0;
e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;e[cnt].w=w;
}
void dfs(int x,ll w){
vis[x]=1;
d[x]=w;
for(int i=head[x];i;i=e[i].ne){
int y=e[i].to;
if(vis[y])T.add(d[x]^d[y]^e[i].w);
else dfs(y,w^e[i].w);
}
}
int main(){
scanf("%d%d",&n,&m);
ll w;
for(int i=1,x,y;i<=m;++i)scanf("%d%d%lld",&x,&y,&w),in(x,y,w),in(y,x,w);
dfs(1,0);
printf("%lld\n",T.sum(d[n]));
}
|
BZOJ2844 albus就是要第一个出场
题目链接
BZOJ 2844
题解
此题实际上为求$k$小线性基的对偶问题，如不考虑重复的话，直接二分皆可解决。考虑上重复的问题，不妨设$cnt$为线性基底个数，那么显然不重复的异或值只有$2^{cnt}$中，即有$n−cnt$个线性无关变量，即每一种异或值都可以经过2n−cnt种变换仍不改变，即每一种异或值共重复了$2^{n−cnt}$次，去重二分后计算上重复次数即可得到答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+1;
const ll mod = 10086;
int n,q[N],Q,cnt;
struct Xor{
int a[N],b[N];
void add(int x){
for(int i=31;i>=0;--i)
if((x>>i)&1)x^=a[i];
for(int i=31;i>=0;--i)
if(((x>>i)&1)&&!a[i]){
a[i]=x;
for(int j=i+1;j<=31;++j)
if((a[j]>>i)&1)a[j]^=x;
return;
}
}
void init(){
cnt=0;
for(int i=0;i<=31;++i)
if(a[i])b[++cnt]=a[i];
}
int kth(int k){
if(k>(1<<cnt))return 2e9;
int ret=0;
for(int i=1;i<=cnt;++i)
if((k>>(i-1))&1)ret^=b[i];
return ret;
}
}T;
ll qpow(ll a,ll b){
ll ret=1;
while(b){
if(b&1)ret=ret*a%mod;
b>>=1;
a=a*a%mod;
}
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&q[i]),T.add(q[i]);
scanf("%d",&Q);
T.init();
int l=0,r=(1<<cnt)-1;
while(l!=r){
int mid=l+r>>1;
if(T.kth(mid)>=Q)r=mid;
else l=mid+1;
}
printf("%d",(1ll+qpow(2,n-cnt)*(ll)l)%mod);
}
|
CQOI2013 新Nim游戏
题目链接
BZOJ 3105
题解
对于后手玩家来说，只要存在多个基底异或值为零，即可将其余所有火柴删除，使得所有最后普通$nim$游戏有异或值为$0$，即后手胜。那么先手玩家为了避免这种情况需要删除所以可能导致异或值为$0$的情况，即可能有线性无关变量的情况（易知不存在先手必败的情况），那么如何将第一个人删除的尽可能少，可以将所有火柴排个序，从大到小插入线性基中，如果为线性无关变量，则直接统计进答案即可。（具体证明需要考虑拟阵，暂时没学）（现在学了，还是不会证）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+1;
int n,a[N];
struct Xor{
int a[32];
bool add(int x){
for(int i=31;i>=0;--i)
if((x>>i)&1)x^=a[i];
for(int i=31;i>=0;--i)
if(((x>>i)&1)&&!a[i]){
a[i]=x;
for(int j=i+1;j<=31;++j)
if((a[j]>>i)&1)a[j]^=x;
return 1;
}
return 0;
}
}T;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
sort(a+1,a+n+1);
ll ans=0;
for(int i=n;i>=1;--i)if(!T.add(a[i]))ans+=a[i];
printf("%lld",ans);
}
|
SCOI2016 幸运数字
题目链接
BZOJ 4568
题解
该题实际上就是将$x$到$y$中所有权值插入线性基中求异或最大值即为答案，观察$n<=20000$的性质，可以通过倍增维护,每次查询启发式合并即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4+1;
int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
struct Xor{
ll a[61];
void add(ll x){
for(int i=60;i>=0;--i)
if((x>>i)&1)x^=a[i];
if(!x)return;
for(int i=60;i>=0;--i)
if(((x>>i)&1)&&!a[i]){
a[i]=x;
for(int j=i+1;j<=60;++j)
if((a[j]>>i)&1)a[j]^=x;
return;
}
}
void init(){
memset(a,0,sizeof(a));
}
ll mx(){
ll ret=0;
for(int i=60;i>=0;--i)
if(((ret>>i)&1)==0)ret^=a[i];
return ret;
}
}g[N][15],R;
Xor mix(Xor a,Xor b){
Xor c;c.init();
int cnta=0,cntb=0;
for(int i=0;i<=60;++i)if(a.a[i])cnta++;
for(int i=0;i<=60;++i)if(b.a[i])cntb++;
if(cnta>=cntb){
for(int i=0;i<=60;++i)c.a[i]=a.a[i];
for(int i=0;i<=60;++i)
if(b.a[i])c.add(b.a[i]);
}
else{
for(int i=0;i<=60;++i)c.a[i]=b.a[i];
for(int i=0;i<=60;++i)
if(a.a[i])c.add(a.a[i]);
}
return c;
}
int head[N],cnt,n,m,Q,f[N][15],d[N],fa[N];
ll a[N];
struct nd{
int to,ne;
}e[N*2];
void in(int x,int y){
e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;
}
void dfs(int x){
for(int i=head[x];i;i=e[i].ne)
if(e[i].to!=fa[x]){
int y=e[i].to;
fa[y]=x;
f[y][0]=x;g[y][0].add(a[x]);
d[y]=d[x]+1;
dfs(y);
}
}
void pre(){
for(int j=1;j<15;++j)
for(int i=1;i<=n;++i){
f[i][j]=f[f[i][j-1]][j-1];
g[i][j]=mix(g[f[i][j-1]][j-1],g[i][j-1]);
}
}
int lca(int x,int y){
R.init();
if(d[x]<d[y])swap(x,y);
for(int i=14;i>=0;--i)
if(d[f[x][i]]>=d[y]){
R=mix(R,g[x][i]);
x=f[x][i];
}
if(x==y)return x;
for(int i=14;i>=0;--i)
if(f[x][i]!=f[y][i]){
R=mix(R,g[x][i]);R=mix(R,g[y][i]);
x=f[x][i],y=f[y][i];
}
R.add(a[f[x][0]]);
return f[x][0];
}
ll solve(int x,int y){
int l=lca(x,y);
R.add(a[x]);R.add(a[y]);
return R.mx();
}
int main(){
n=read();Q=read();
for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
for(int i=1,x,y;i<n;++i)x=read(),y=read(),in(x,y),in(y,x);
d[1]=1;dfs(1);
pre();
for(int i=1,x,y;i<=Q;++i)printf("%lld\n",solve(read(),read()));
}
|
