Acwing 216. Rainbow的信号 题解
题目描述
Freda发明了传呼机之后,rainbow进一步改进了传呼机发送信息所使用的信号。
由于现在是数字、信息时代,rainbow发明的信号用N个自然数表示。
为了避免两个人的对话被大坏蛋VariantF偷听,rainbow把对话分成A、B、C三部分,分别用a、b、c三个密码加密。
现在Freda接到了rainbow的信息,她的首要工作就是解密。
Freda了解到,这三部分的密码计算方式如下:
在1~N这N个数中,等概率地选取两个数l、r,如果l>r,则交换l、r。把信号中的第l个数到第r个数取出来,构成一个数列P。
A部分对话的密码是数列P的xor和的数学期望值,xor和就是数列P中各个数异或之后得到的数; xor和的期望就是对于所有可能选取的l、r,所得到的数列的xor和的平均数。
B部分对话的密码是数列P的and和的期望,定义类似于xor和。
C部分对话的密码是数列P的or和的期望,定义类似于xor和。
请你帮忙计算这三个密码。
思路
蒟蒻的思路当然是来自《算法竞赛进阶指南》,只是加入一些自己的理解。
按位计算答案。枚举二进制下的每个数位,数的大小不超过10^9^,所以最多枚举到30位。
对每一位,枚举1到n每个数,把当前枚举的第k个数当做选取范围的右端点r,利用先前维护的值来更新答案。
设当前的枚举的数位为k,当前枚举的是第r个数,当前第r个数的数位的值为v(0或1)。
首先知道:l = r 的情况概率为 1 / n^2,其他情况均为 2 / n^2(因为有( l , r ) , ( r , l )两种选法,当r>l时二者交换),在加入答案时注意乘以2。
当前数位的值v为1时
因为有l = r 的情况,所以xor,and,or的答案都要加上该数位的值(若是第3数位则值为100即十进制下的4)除以n^2^的概率(设为pos)。
对于 or 和,l 取 r 前面的任意值,[ l, r ]的或(or)值都为1,共有(r-1)种情况,对答案 ansor 贡献(r-1)* pos。
对于 and 和,我们用 last[v]表示上个v出现的位置,只有当前数位的值为1时才能加入答案,因为如果 [ l, r ] 区间有一个值为0则and值立刻变成0了。而 l 的取值范围的数位 k 的值必须为1,这时候就需要用到 last 数组,l 可以选择的区间即为 [ last[0]+1,r ] 。
当前数位的值v为0时
对于 or 和,l 可以取的区间中的数位值必须有一个 1 ,这样异或后的值才会为一,因为last[1] 到 r 之间的数位值都是0,所以该区间不能取,可取的区间为 [1,last[1] ]。
xor 和的讨论有点麻烦,单独列出来。
对于某个数位上,1到n各个数在该数位的数位值,当前为第 r 个数:
以1为边界将区间分段,为方便理解我将它们编个号:
当l取1、3、5区间时,[ l , r ] 数位值的xor和为0;l取2、4、6区间时,[ l , r ] 数位值的xor和为1。
发现了吗,每个区间都只有一个1。异或0对xor和的值无影响;而每异或一次1,xor和的值就会由1变0或由0变1,所以我们用c1表示奇数区间包含的值的个数,c2表示偶数区间包含的值的个数。
当前数位值为0,l 有c2个可能取值使 [ l , r ] 的xor和为1;当前数位值为1,l 有c1个可能取值使 [ l , r ] 的xor和为1。
c1,c2的维护可通过看下面的代码理解
代码:
#include<bits/stdc++.h>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
const int maxn=1e5+5;
int n,c1,c2;
int w[maxn],p[maxn],last[2];
double ansxor,ansand,ansor;
void solve(int k)
{
c1=c2=0;
last[0]=last[1]=0;
double pos=(double)(1<<k)/n/n;//当前数位的实际值/n方的概率
for(int r=1;r<=n;r++)
{
int v=((w[r]>>k)&1);
if(v)
{
ansxor+=pos;
ansand+=pos;
ansor+=pos;
}
if(v)
{
ansor+=pos*(r-1)*2;
ansand+=pos*(r-1-last[0])*2;
ansxor+=pos*c1*2;
}
else
{
ansor+=pos*last[1]*2;
ansxor+=pos*c2*2;
}
++c1;
if(v) swap(c1,c2);
last[v]=r;
}
}
int main()
{
//freopen("input.txt","r",stdin);
n=read();
for(int i=1;i<=n;i++) w[i]=read();
for(int i=0;i<=30;i++) solve(i);
printf("%.3lf %.3lf %.3lf",ansxor,ansand,ansor);
return 0;
}
蒟蒻第一次发题解,不足请大佬指正。
另外,能骗个赞吗QAQ
终于懂了
%%%大佬太强了。
按位计算答案必须要从0到30枚举吗,能从30到0枚举吗
当然可以,两者并无区别
666
麻蛋,怎么能这么强,插眼了
%%%%%%%
dalao
瓷资
神仙
数论之王
您这么谦虚,对得起您的id吗?
期望皇帝
%%%%%%%%%%%%%%%%%%%%%%