3811: 玛里苟斯
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 500 Solved: 196
[Submit][Status][Discuss]
Description
魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心，于是他想了一道数学题。
S 是一个可重集合，S={a1,a2,…,an}。
等概率随机取 S 的一个子集 A={ai1,…,aim}。
计算出 A 中所有元素异或 x, 求 xk 的期望。
Input
第一行两个正整数 n, k。
以下 n 行每行一个整数，表示 ai。
Output
如果结果是整数，直接输出。如果结果是小数（显然这个小数是有限的），输出精确值（末尾不加多余的 0）。
Sample Input
4 2
0
1
2
3
Sample Output
3.5
HINT
限制与约定
1≤n≤100000，1≤k≤5，ai≥0。最终答案小于 2^63 。k=1,2,3,4,5 各自占用 20% 的数据
Source
题解：
wwwwodddd ORZ
求子集异或和k次方的期望；
首先这和期望的k次方不一样，所以还是老老实实按k分类讨论，按位算贡献吧：
k=1 , 考虑第i位是否有1，有会贡献的$2^{i-1} $, 全部或起来除二；
k=2，如果某个异或和的第i位和第j为都有值，会贡献$2^{i+j}$的答案 ， 首先这两位都必须要有至少一个1；
紧接着如果对于每一个数来说，这两位的值都相同 ，说明两位不相互独立，所以概率是1/2,期望是$2^{i+j-1}$;
否则说明两位独立，在异或运算下(0,0)(0,1)(1,0)(1,1)的概率相同为1/4，期望是$2^{i+j-2}$;
k>=3 , 由于答案在2^63次方以内，所以线性基的大小不会超过22，直接暴力枚举计算期望；
这题有一个结论是答案*2一定是整数；
也就是答案的小数最多有一位；
这里有个评论证明了，但是我没太看懂： https://blog.sengxian.com/solutions/bzoj-3811 自己给出一个可能不太严谨的证明吧（没学过数学。。。）： 可以仔细分析一下k==2时的算法；
再扩展到k次方，发现在异或运算下：
二进制位之间贡献不相互独立是具有传递性的；
假设一次计算答案时选定的k个二进制位(可能相同分)集合为：
B = {b1,b2,...bk}
我们可以把他们进一步分成m个集合：
S1...Sm
相同集合元素贡献不互相独立，不同集合贡献互相独立；
这时对答案期望的贡献应该是2^{b1+b2+...+bk - m} ;
而k >= m ， 且B里面至少有m个不同的二进制位(即bi!=bj这种)；
所以考虑b1+b2+...+bk - m最小的情况：
分析可以发现最小为-；
所以答案小数点后只有一位； 。。。。。。
如果你感兴趣的话
这样就可以用一个数存下对2^|B|的除数和余数，分类讨论小数位的情况（建议看下代码）；
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define Run(i,l,r) for(int i=l;i<=r;i++)
#define Don(i,l,r) for(int i=l;i>=r;i--)
#define ll unsigned long long
#define ld long double
#define inf 0x3f3f3f3f
using namespace std;
const int N=;
int n,m,cnt;
ll a[N],d[],res,ans;
char gc(){
static char*p1,*p2,s[];
if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
ll rd(){
ll x=; char c=gc();
while(c<''||c>'')c=gc();
while(c>=''&&c<='')x=(x<<)+(x<<)+c-'',c=gc();
return x;
}
void solve1(){
Run(i,,n){
ll x=rd();
ans|=x;
}
printf("%llu",ans>>);
if(ans&)printf(".5\n");
else puts("");
}
void solve2(){
Run(i,,n)a[i]=rd();
for(int i=;i<=;i++)
for(int j=;j<=;j++){
int fg1=,fg2=,fg3=;
for(int k=;k<=n;k++){
if(a[k]>>i&)fg1=;
if(a[k]>>j&)fg2=;
if((a[k]>>i&)!=(a[k]>>j&))fg3=;
if(fg1&&fg2&&fg3)break;
}
if(!fg1||!fg2)continue;
if(i+j-fg3-<)res++;
else ans+=1ull<<(i+j-fg3-);
}
ans+=res>>; res&=;
printf("%llu",ans);
if(res)printf(".5\n");
else puts("");
}
void solve3(){
for(int i=;i<=n;i++){
ll x=rd();
for(int j=;~j;j--)if(x>>j&){
if(!d[j]){d[j]=x;break;}
else x^=d[j];
}
}
for(int i=;i<=;i++)if(d[i])a[cnt++]=d[i];
for(int i=;i<<<cnt;i++){
ll x=;
for(int j=;j<cnt;j++)if(i>>j&)x^=a[j];
ll t1=,t2=;
for(int j=;j<=m;j++){
t1*=x , t2*=x;
t1 += t2 >> cnt , t2 &= (<<cnt) - ;
}
ans += t1 , res += t2;
ans += res >> cnt , res &= (<<cnt) - ;
}
printf("%llu",ans);
if(res)printf(".5\n");
else printf("\n");
}
int main(){
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
n=rd(); m=rd();
if(m==)solve1();
else if(m==)solve2();
else solve3();
return ;
}//by tkys_Austin;