专栏文章

题解：P10500 Rainbow的信号

UUsstzqqch_Iroha
P10500题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio7rypl
此快照首次捕获于
2025/12/02 14:45
3 个月前
此快照最后确认于
2025/12/02 14:45
3 个月前
查看原文
来源：《算法竞赛进阶指南》，李煜东著，0x38\texttt{0x38}。
原题：AcWing216\texttt{AcWing216}。
蒟蒻刚开始做的时候没看懂题解和小蓝皮。后来自己琢磨了一会自己就想通了（其实可能是书里的表述没太看懂），所以现在写一篇比较浅显的题解。
由于这可以算是数学期望的模板题，所以首先对于数学期望，我们来做一些解释。先来看前置知识。
  • 随机事件 AA：可能有多种结果的事件。
  • 样本点：事件 AA 的某种可能结果。
  • 样本空间 Ω\Omega：指某随机事件 AA 的所有可能达成的状态（样本点）组成的集合。
  • 概率 P(A)P(A)：指事件 AA 发生的结果个数占总结果个数（即样本空间）的比重。
  • 随机变量 XX：将样本点映射为实数的函数。我们讨论取值有限的离散型随机变量。
有了这些知识，我们来了解数学期望的定义。
若随机变量 XX 的取值有 x1,x2...x1,x2...，一个随机事件可表示成 X=XiX=X_i，其概率为 P(X=Xi)=piP(X=X_i)=p_i，则称 E(x)=ΣpixiE(x)=\Sigma p_ix_i 为随机变量 XX 的数学期望。摘自《算法竞赛进阶指南》，李煜东著。
说白了，数学期望就是带权求和，只是权值变成了事件发生的概率，这需要你自己求；而随机变量通常题目里面会给你求法或者定义。
譬如：本题当中给定了你随机变量 XX 的求法，即任意选定的区间 [L,R][L,R] 中所有的 NiN_i 的按位 xor,or,and\text{xor,or,and} 和，而概率则需自己计算。
首先计算概率。根据题意，显然 l<rl<r 时会有一个 r<lr<l 的对称情况，P(A)=1n×1n×2=2n2P(A)=\displaystyle \frac{1}{n}\times \displaystyle \frac{1}{n}\times 2 = \displaystyle \frac{2}{n^2} 。同理 l=rl=r 时 P(A)=1n2P(A)=\displaystyle \frac{1}{n^2}。
现在的问题就是处理区间内的位运算。显然采用前缀异或/与/或数组会达到 O(n2)O(n^2) 的时间复杂度，会爆。考虑到位运算不进位，我们可以将整数转换为二进制，按位进行计算，最后合并每一位的贡献即可。
有了这个思路，接下来就是分类讨论了。（然后挂了我很久）
首先我们设目前枚举到了NiN_i 的第 kk 个二进制数位（从 11 开始）为右边界，目前称之为 BiB_i（因为我们之后还要更新）。我们先对朴素的按位与和按位或进行讨论。
记该位之前数字 gg 最后一次出现过的位置为 last[g]last[g]，那么我们稍加思索可以推出以下结论：
  1. 按位或：当 Bi=1B_i=1 时，对于任意的 l≤rl\le r，区间 [l,r][l,r] 内的 or\text{or} 和的结果一定为 11。这是因为按位或“有 11 全 11”的性质（即 1 or x=11\ \text{or}\ x = 1）。此时将 2k−1×P(A)×(r−1)2^{k-1}\times P(A)\times (r-1) 累加到 or\text{or} 的答案中。
  2. 按位与：当 Bi=0B_i=0 时，对于任意的 l≤rl\le r，区间 [l,r][l,r] 内的 and\text{and} 和的结果一定为 00。这是因为按位与“有 00 全 00”的性质（即 0 and x=00\ \text{and}\ x=0）。此时对 and\text{and} 的答案什么都不做。
  3. 当 Bi=0B_i=0 时，将 2k−1×P(A)×last[1]2^{k-1}\times P(A)\times last[1] 累加到 or\text{or} 的答案中（如果出现过 11 的话）。
  4. 当 Bi=1B_i=1 时，将 2k−1×P(A)×(k−last[0]−1)2^{k-1}\times P(A)\times (k-last[0]-1) 累加到 and\text{and} 的答案中（如果出现过 00 的话）。
接下来我们开始讨论 xor\text{xor} 的情况。
我们知道 xor\text{xor} 运算和其它运算都不太一样。 xor\text{xor} 运算不仅仅和当前数位有关，它和前面的所有数位 xor\text{xor} 的结果也有关系。所以我们可以开两个变量 c0c_0、c1c_1 来记录所有的 ll 的个数，分别满足 xori=lk−1Bi=0 \text{xor}^{k-1}_{i=l} B_i=0 和 xori=lk−1Bi=1 \text{xor}^{k-1}_{i=l} B_i=1。那么当 Bi=0B_i=0 时，将 2k−1×P(A)×c12^{k-1}\times P(A)\times c_1 累加到答案中，反之将 2k−1×P(A)×c02^{k-1}\times P(A)\times c_0 累加到答案中，并需要将 c0c_0 和 c1c_1 进行交换（因为原来 [l,k−1][l,k-1] 的 xor\text{xor} 结果为 00，xor 1\text{xor}\ 1 运算过后结果变成了 11，而原来 c1c_1 对应的区间 xor\text{xor} 的结果就变成了 00）。注意我们需要在交换之前 c0←c0+1c_0\gets c_0+1 来更新之后的 c1c_1。
代码其实写出来也差不多，但还是粘上来吧。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n;
int N[maxn];
int pre_xor[maxn],pre_and[maxn],pre_or[maxn];
int /*B[maxn],*/last[2];//开一个B变量就够了
double ans_xor,ans_and,ans_or;
int maxk = -1,len;
/*int calc(int x){
	int y=x;
	len = 0;
	while(y){
		y>>=1;
		len++;
	}
	return len;
}*/
//试图计算最大位数发现没有必要 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>N[i];
	}
	/*for(int i=1;i<=n;i++){
		maxk = max(maxk,calc(N[i]));
	}*/
  //调试代码
	int c1,c2;
    for(int k=0;k<=30;k++){//这里是从第0位开始的
    	last[0]=0;
    	last[1]=0;
    	c1=0;
    	c2=0;
    	for(int i=1;i<=n;i++){
    		int B = (N[i]>>k)&1;
    		double ret = (double)(1<<k)/(n*n);
    		if(B==0){
    			ans_and+=ret+2.0*ret*(i-last[0]-1);
    			ans_or+=ret+2.0*ret*(i-1);
    			ans_xor+=ret+2.0*ret*c1;
			}
			else{
				ans_or+=2.0*ret*last[1];
				ans_xor+=2.0*ret*c2;
			}//按上面的结论模拟
			last[B]=i;
			c1++;
			if(B) swap(c1,c2);
		}
	}
	printf("%.3f %.3f %.3f",ans_xor,ans_and,ans_or);
}

一些提醒

  1. 注意浮点数类型不要开 long double\texttt{long double}。因为你会发现你的程序除了 0.0000.000 什么都不输出。是的我第一遍就挂在这里
  2. 涉及乘法，记得开 long long\texttt{long long}。否则你会由 40←10040\gets 100，这很不好笑。实例。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...