2017-07-05

【清华集训2014】玛里苟斯

线性基重学系列第三题

AC通道

清华集训的题果然都是神题

早就听说过这道神题，一直都不敢碰，今天复习线性基，终于A掉了（好开心啊

粘个题解：（有上好的现成题解为何不用？

传送门

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
using namespace std;
typedef unsigned long long ll;
int n,K,cnt;
ll a[MAXN],b[25],Mat[25];
inline ll read(){
	ll x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void solve1(){
	ll ans=0;
	for(int i=1;i<=n;++i) ans|=a[i];
	printf("%lld",ans>>1);
	if(ans&1) printf(".5");
	printf("\n");
}
void solve2(){
	ll ans=0,res=0;
	for(int i=32;i>=0;--i)for(int j=32;j>=0;--j){
		bool flag; 
		flag=0; for(int k=1;k<=n;++k)if(a[k]>>i&1)flag=1; if(!flag) continue;
		flag=0; for(int k=1;k<=n;++k)if(a[k]>>j&1)flag=1; if(!flag) continue;
		flag=0; for(int k=1;k<=n;++k)if((a[k]>>i&1)!=(a[k]>>j&1))flag=1;
		if(i+j-1-flag==-1) res+=2;
		else if(i+j-1-flag==-2) res++;
		else ans+=(1LL<<(i+j-1-flag));
	}
	ans+=(res>>2);  res%=4;
	printf("%lld",ans);
	if(res==1) printf(".25");
	else if(res==2) printf(".5");
	else if(res==3) printf(".75");
	printf("\n");
}
void solve3(){
	ll ans=0,res=0;
	for(int i=1;i<=n;++i)for(int j=23;j>=0;--j)if(a[i]>>j&1){
		if(Mat[j]) a[i]^=Mat[j];
		else{
			Mat[j]=a[i];
			for(int k=j-1;k>=0;--k) if(Mat[k]&&(Mat[j]>>k&1))Mat[j]^=Mat[k];
			for(int k=j+1;k<=23;++k)if(Mat[k]&&(Mat[j]>>k&1))Mat[k]^=Mat[j];
			break;
		}
	}
	for(int i=0;i<=23;++i)if(Mat[i])b[++cnt]=Mat[i];
	for(int i=0;i<(1<<cnt);++i){
		ll ret=0,Shang=0,Yu=1;
		for(int j=1;j<=cnt;++j)if(i&(1<<(j-1)))ret^=b[j];
		for(int j=1;j<=K;++j){
			Shang*=ret;  Yu*=ret;
			Shang+=Yu>>cnt;  Yu%=(1<<cnt);
		}
		ans+=Shang;  res+=Yu;
		ans+=res>>cnt;  res%=(1<<cnt);
	}
	printf("%lld",ans);
	if(res) printf(".5");
	printf("\n");
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  K=read();
	for(int i=1;i<=n;++i) a[i]=read();
	if(K==1) solve1();
	else if(K==2) solve2();
	else solve3();
	return 0;
}

本文标题:【清华集训2014】玛里苟斯

文章作者:chty

发布时间:2017年07月05日 - 19时28分

最后更新:2018年06月08日 - 18时46分

许可协议:本文为博主原创，未经许可不得转载。