「bzoj3811」玛里苟斯 - 分类讨论+线性基 | Bill Yang's Blog

「bzoj3811」玛里苟斯 - 分类讨论+线性基

题目大意

    魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心,于是他想了一道数学题。
    $S$是一个可重集合,$S=\lbrace a_1,a_2,\ldots,a_n\rbrace$。
    等概率选取$S$的一个子集$A=\lbrace {a_i}_1,\ldots,{a_i}_m\rbrace$。
    计算出$A$中所有元素的异或和$x$,求$x^k(1\le k\le5)$的期望。


题目分析

根据条件$1\le k\le5$,考虑对$k$进行分类讨论。

  1. $k=1$:
    因为题目是随意选择子集,故每个数被选的概率是$\frac12$。
    对每一位进行考虑,若存在第$i$位为$1$的数,那么选出奇数个$1$和选出偶数个$1$的概率均为$\frac12$,那么贡献即为$\frac{2^i}2$。
    对于不存在第$i$位为$1$的数,显然贡献为$0$。

  2. $k=2$:
    我们求的是每个异或和平方的期望。
    因此每个异或和的贡献是$(b_mb_{m-1}\cdots b_0)_2(b_mb_{m-1}\cdots b_0)_2$,写成卷积的形式就是:$\sum_i^m\sum_j^mb_ib_j\cdot2^{i+j}$。
    我们枚举$i,j$两个二进制位,每个数即可看做一个$(0/1,0/1)$二元组,仅当所有数异或后得到二元组$(1,1)$,才会产生$2^{i+j}$的贡献,再次分类讨论。

    • 所有数$i,j$位其中一位均为$0$:产生$0$的贡献。
    • 所有数构成的二元组均为$(1,1)$或$(0,0)$,且至少有一个$(1,1)$:退化为$k=1$的情况,有$\frac12$的概率产生$2^{i+j}$的贡献。
    • 否则,因为对于每一位出现奇数个$1$的概率均为$\frac12$,因此有$\frac14$的概率产生$2^{i+j}$的贡献。
      显然,因为答案$\lt2^{63}$,因此每个数$\lt2^{32}$,时间复杂度为$O(32^2n)=102400000$,可以卡过。
  3. $k\ge3$:
    此时我们使用类似$k=2$的方法就会超时了。
    此时每个数$\lt2^{22}$,我们发现线性基向量最多$22$个,直接构造线性基$\frak B$后枚举子集。
    枚举线性基的子集,得到异或和$v$,根据bzoj2844所讲,可以发现异或和$v$出现次数均为$2^{n-\left|\frak B\right|}$,因此期望即为$p\times v=\frac{2^{n-\left|\frak B\right|}}{2^n}\times v=\frac v{2^{\left|\frak B\right|}}$。
    直接统计即可,时间复杂度为$O(2^{22}\cdot22)=92274688$,再次卡过。

注意:虽然答案在$long\,long$范围内,但是中间统计答案的时候可能会溢出,因此在$k\neq1$时,若除数为$2^m$,我们可以将答案记作$s=\lfloor\frac s{2^m}\rfloor\cdot2^m+y\bmod2^m$的形式,这样两个项都不会溢出。

考虑输出小数的问题。
结论:小数位只可能是$0$或$0.5$。
证明:
首先$k=1,2$时显然成立。
当$k\gt2$时:
设线性基最多有$\left|\frak B\right|$位。
对于每一位,若该位为$0$,显然不会对小数部分产生贡献。
若该位为$1$,因为枚举所有子集,所以该位的$1$会被统计$\frac{2^{\left|\frak B\right|}}2=2^{\left|\frak B\right|-1}$次。
对于每一位均是如此,因此我们只需要考虑进位即可。
显然低位的$1$会被传递到其前$\left|\frak B\right|-1$位才会停止进位($2$的整数幂次),即最高位,而分母部分是$2^{\left|\frak B\right|}$,因此最多会对一个小数位产生影响。
因此,结论得证。


代码

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef unsigned long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
int n,k;
LL a[maxn];
namespace Solve1 {
void solve() {
LL ans=0;
for(int i=1; i<=n; i++)ans|=a[i];
printf("%llu",ans>>1);
if(ans&1)puts(".5");
}
}
namespace Solve2 {
const int MAX_BASE=32;
LL ans=0,remain=0;
void solve() {
for(int i=0; i<MAX_BASE; i++)
for(int j=0; j<MAX_BASE; j++) {
bool bj=0;
for(int k=1; k<=n; k++)
if(a[k]>>i&1) {
bj=1;
break;
}
if(!bj)continue;
bj=0;
for(int k=1; k<=n; k++)
if(a[k]>>j&1) {
bj=1;
break;
}
if(!bj)continue;
bj=0; //统计是否全为$(1,1),(0,0)$
for(int k=1; k<=n; k++)
if((a[k]>>i&1)!=(a[k]>>j&1)) {
bj=1;
break;
}
if(i+j-1-bj<0)remain++;
else ans+=1ll<<(i+j-1-bj);
}
ans+=remain>>1;
printf("%llu",ans);
if(remain&1)puts(".5");
}
}
namespace Solve3 {
const int MAX_BASE=22;
LL ans=0,remain=0;
struct Linear_Bases {
vector<LL>a;
LL b[MAX_BASE+5];
void add(LL num) {
for(int j=MAX_BASE; j>=0; j--)
if(num>>j&1) {
if(b[j]) {
num^=b[j];
continue;
}
b[j]=num;
for(int k=j-1; k>=0; k--)if(b[j]>>k&1)b[j]^=b[k];
for(int k=j+1; k<=MAX_BASE; k++)if(b[k]>>j&1)b[k]^=b[j];
break;
}
}
void build(int n,LL* a) {
for(int i=1; i<=n; i++)add(a[i]);
}
void split() {
for(int j=MAX_BASE; j>=0; j--)if(b[j])a.push_back(b[j]);
}
} lb;
void solve() {
lb.build(n,a);
lb.split();
int size=lb.a.size();
for(int i=(1<<size)-1; i>=0; i--) {
int val=0;
for(int j=0; j<size; j++)if(i>>j&1)val^=lb.a[j];
LL a=0,b=1;
for(int j=1; j<=k; j++) {
b*=val;
a=a*val+(b>>size);
b&=(1<<size)-1;
}
remain+=b;
ans+=a+(remain>>size);
remain&=(1<<size)-1;
}
printf("%llu",ans);
if(remain)puts(".5");
}
}
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
if(k==1)Solve1::solve();
else if(k==2)Solve2::solve();
else Solve3::solve();
return 0;
}
0%