Fork me on GitHub

Uoj#36.【清华集训2014】玛里苟斯

Uoj#36. 【清华集训2014】玛里苟斯

题意:

  • 求可重集合$S$的子集异或和的$k$次方期望值。
  • 答案保证在$long\ long$范围内。
  • $1\le n\le 100000,1\le k\le 5$。

题解:

  • 这(可以)是一道数据分类题。
  • 根据题意发现$a_i^k<2^{63}$,所以$a_i<2^{\frac{63}{k}}$。
  • $m=\lfloor \log_2 (max_{i=1}^{n}a_i) \rfloor$。
  • 那么$m\le \frac{63}{k}$。

$k=1$

  • 答案显然是总异或和的一半。
  • 可以考虑建出$n$个数的线性基,显然对于每一个可以为$1$的位,它为$0,1$的概率完全相同。
  • 所以每一位的贡献都恰好一半。

$k>2$

  • 显然此时$a_i< 2^{21}$。
  • 线性基中最多$21$个数。
  • 我们暴力枚举选择的集合计算即可。

$k=2$

  • 设$P=\{a_0,a_1,\cdots,a_{2^n-1}\}$。
  • 答案为
  • 设$b_{i,j}$为$a_i$二进制第$j$位。
  • 而$\frac{\sum_{i=0}^{2^n-1}(b_{i,j}b_{i,p})}{2^n}$分$j=p$和$j\not=p$讨论即可。

代码:

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
#include <bits/stdc++.h>
#define N 100009
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef __int128 lll;
int n,k;
llu a[N],Ans,sum;
struct LB
{
llu a[64],t,s[64];
int num;
void insert(llu x)
{
for (int i=63;~i;--i)
if (x>>i&1llu)
{
if (!a[i])
{
a[i]=x;
t^=1llu<<i;
num++;
break;
}
else x^=a[i];
}
}
void work()
{
for (int i=0;i<64;i++)
for (int j=0;j<64;j++)
if (a[i]>>j&1) s[j]|=1<<i;
}
}lb;
lll get(int x,llu y)
{
return (lll)x*x*x*(y>=4?x:1)*(y==5?x:1);
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%llu",&a[i]),sum|=a[i];
if (k==1) Ans=sum;
else
{
for (int i=1;i<=n;i++)
lb.insert(a[i]);
lb.work();
if (k>2)
{
lll ret=0;
for (llu i=lb.t;i;i=(i-1)&lb.t)
{
int now=0;
for (int j=0;j<22;j++)
if (i>>j&1) now^=lb.a[j];
ret+=get(now,k);
}
Ans=ret>>(lb.num-1);
}
else
{
for (int i=0;i<32;i++)
for (int j=0;j<32;j++)
if ((sum>>i&1)&&(sum>>j&1))
Ans+=1llu<<(i+j-(lb.s[i]!=lb.s[j]));
}
}
printf("%llu%s",Ans/2,Ans&1llu?".5\n":"\n");
return 0;
}
-------------本文结束感谢您的阅读-------------

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

文章作者:wzf2000

发布时间:2018年04月18日 - 15:04

最后更新:2018年04月27日 - 11:04

原始链接:https://wzf2000.github.io/2018/04/18/Uoj36/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。