清华集训2014 玛里苟斯

题面

upd:结论证明已加入

题解

k=1

对于每一位分开考虑。

如果这一位可能被异或出来,那么就有1/21/2的概率出现。

直接计算即可。

k=2

ans=i=031j=031di,j2i+j ans=\sum_{i=0}^{31}\sum_{j=0}^{31}d_{i,j}2^{i+j}

其中di,jd_{i,j}表示异或和中2i,2j2^i,2^j这两位同时出现的概率。

di,jd_{i,j}怎么计算呢?

如果任意一位不可能出现,为0。

如果不可能独立出现,为12\frac{1}{2}

否则为14\frac{1}{4}

k>2

由于k比较大,答案<263<2^{63},所以每个数<222<2^{22}

那么线性基不超过22个数。

维护线性基直接暴力就可以了。

一个奇怪的结论

对于任意k,答案的小数部分要么是0要么是0.5。

当k=1和k=2时可以根据算法过程证明。

upd:结论的证明:参考sengxian博客下的评论(Orz Bill Yang)

Orz Bill Yang

考虑一个显然的思路:枚举k个位a1..aka_1..a_k(每一位互相独立且有顺序可以相同),然后计算这k位同时为1的概率×2ai\times 2^{\sum a_i}求和。(也就是k=2的方法)

如果其中任意一位不可能为1,则概率为0(显然不影响)

如果概率为12i\frac{1}{2^i},则a1..aka_1..a_k中至少有i个不同的项,那么至少有一项i1\ge i-1,那么它对2ai2^{\sum_{a_i}}就至少有2i12^{i-1}的贡献。

然后2i1×12i=122^{i-1}\times\frac{1}{2^i}=\frac{1}{2}就抵消掉了。

所以答案就只会有12\frac{1}{2}而不是14\frac{1}{4}等。

(如果是伪证欢迎disqus评论打脸)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
Author: CNYALI_LK
LANG: C++
PROG: malygos.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef unsigned long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
ll linear[66],basis[66],k,s[66],a[233333];
void insert(ll x){
for(ll i=60;~i;--i){
if(x&(1LL<<i))
if(linear[i]) x^=linear[i];
else{
linear[i]=x;
for(ll j=i-1;~j;--j)if(linear[i]&(1LL<<j))linear[i]^=linear[j];
for(ll j=60;j>i;--j)if(linear[j]&(1LL<<i))linear[j]^=linear[i];
k=0;
for(ll j=0;j<60;++j)if(linear[j]){basis[k]=linear[j];++k;}
break;
}
}

}
int main(){
#ifdef cnyali_lk
freopen("malygos.in","r",stdin);
freopen("malygos.out","w",stdout);
#endif
ll n,m;
n=read();
m=read();
for(ll i=1;i<=n;++i)a[i]=read();
if(m==1){
ll ans=0;
for(ll i=1;i<=n;++i)ans|=a[i];
if(ans&1)printf("%llu.5\n",ans>>1);
else printf("%llu\n",ans>>1);
}
else if(m==2){
ll res=0,ans=0;
for(ll i=0;i<32;++i)for(ll j=0;j<32;++j){
ll as,b,c;
as=b=c=0;
for(ll k=1;k<=n;++k){
if(!!(a[k]&(1LL<<i))!=!!(a[k]&(1LL<<j)))as=1;
if(a[k]&(1LL<<i))b=1;
if(a[k]&(1LL<<j))c=1;
}
if(b&&c){
if((int)(i+j)-1-(int)as<0)++res;
else{
ans+=1ULL<<(i+j-1-as);
}
}
}
ans=ans+(res>>1);
res&=1;
printf("%llu%s",ans,res?".5\n":"\n");
}
else{
for(ll i=1;i<=n;++i)insert(a[i]);
ll ans=0,res=0;
for(ll i=0;i<(1<<k);++i){
ll as=0,xres=1,sum=0;
for(ll j=0;j<k;++j)if(i&(1<<j))as^=basis[j];
for(ll l=1;l<=m;++l){
sum=sum*as;
xres=xres*as;
sum+=xres>>k;
xres&=(1<<k)-1;
}
res+=xres;
ans+=sum+(res>>k);
res&=(1<<k)-1;
}
printf("%llu%s",ans,res?".5\n":"\n");
}
return 0;
}
文章目录
  1. 1. 题解
    1. 1.1. k=1
    2. 1.2. k=2
    3. 1.3. k>2
  2. 2. 一个奇怪的结论
  3. 3. 代码
|

博客使用Disqus作为评论系统