HJA的异或值

• 查看
• 提交
• 统计
• 提问

总时间限制: 

20000ms

 

内存限制: 

512000kB

描述

形态形成场（Morphogenetic Field）假说是Rupert Sheldrake提出的一种“共鸣”理论，是事件的共鸣。连续发生同类事件的场所被称为“形态形成场”，所发生的同类事件则被称为“形态共鸣”。

有一个验证这一假说的著名实验：将860只白鼠等分成两批，在相距10.8英里的两个实验室进行三个阶段的实验。

第一阶段在实验室A用300只进行一项简易的迷宫实验，让一只白鼠进入简易迷宫盒，测量其通过的时间，一次实验用10只白鼠在10个迷宫盒中同时进行，如此进行30次。而得到的数据显示，从第4次实验开始白鼠的平均通过时间都会在小范围内比前次短一些。

第二阶段在完成第一阶段的72小时之后，仍在实验室A用剩余的130只白鼠，使用相同的迷宫盒进行实验，而这次平均通过时间较第一阶段的平均时间短了20秒。

第三阶段在完成第二阶段的10天之后，在实验室B进行。这次实验使用了430只白鼠和10个全新的迷宫盒。而令人吃惊的是，所有白鼠都是以最短的路线走完迷宫，时间都在28秒左右。完全没有过交流的两批白鼠在不同时间和地点做同一种实验，竟然有“积累经验”的效果。

尽管如此，白鼠和人类在构造上还是存在一定的差距。而关于人类与形态形成场的关系，也有过一个实验，被称为密室实验。两批被实验者分别被关在两个不同的屏蔽的信号的密室，从密室B逃脱需要解开一个机关，而密室A内有解开机关的线索。在密室A中的人无法通过任何通讯手段和密室B中的人联系，而密室B中的人凭自身力量也是无法从密室中逃脱的。实验进行了9个小时，最后密室B中的一个小女孩解开了机关。事后小女孩回忆，自己在尝试解开机关的时候产生了幻觉，似乎有人在和她交流，等她从幻觉中反应过来的时候，她自己已经在解开机关的途中了，而剩下的部分她也知道该如何操作。密室A中也有人说自己似乎在和一个不在房间内的人交谈，而这个人正是密室B中小女孩的哥哥。

形态形成场假说对此的解释是，存在这样一个形态形成场，存储了关于特定事件的信息。生物可以作为“读取者”或者“写入者”对形态形成场的信息进行增添或者修改。每个人“读取”和“写入”的能力是不一样的，“读取”和“写入”的双方之间也存在着一种类似“同步”的概念，基因相近的人之间的“同步”较其他人来说可能较为容易。一个可以支撑这一解释的例子是许多双胞胎之间的心灵感应现象。

下面是在密室实验中的一个子机关。密室A中有一台机器，它会在内等概率随机一个数，记作。密室B中有另一台机器，要求密室B中的人输入另一个内的数，记作。机关解除要求对于给定的，令表示异或，表示与的异或值，使得达到最大值。

密室A中的人可以算出应输入的值，并尝试通过形态形成场传递给密室B中的人。假设传递的成功率为。如果传递成功，那么密室B中的人就会输入传递的值，否则会在内等概率随机输入一个数作为的值。请求出，对于一组确定的和的值，的期望值是多少？

 

输入

输入数据仅包含一行，其中有一个正整数和一个实数，含义如题目描述中所述。至多精确到小数点后位。

输出

输出一行，用科学计数法表示的期望值。输出一个实数和一个非负整数，表示，其中。特别地，如果答案为，那么。
因为openjudge没有spj,所以请保留八位小数

样例输入

【样例输入1】3 0.5【样例输入2】123456 0.5

样例输出

【样例输出1】2.000000 0【样例输出2】9.806367 4

提示

n <= 10^18

来源

zhonghaoxi

本題難點在於給定一個n，對於1~n中每個k，存在1<=a<=n，使得k^a最大，求所有k^a之和。

這個問題確實不太好想，我們先要瞭解如下幾點：

1. 在同類題目中，都有高位完全優先的性質，即只要高位能取到最優解，其他位置完全不用考慮。
2. 如果處理整個數字沒有思路，可以嘗試安慰分解，對於每一位單獨處理。

在本題中，就運用了以上兩點，我們從最高非零位向下枚舉，

　　如果n的這一位爲1，那麼對於1～n所有數，其最大異或結果這一位一定爲1

　　如果這一位爲0，那麼如果前面不存在退位現象，即本可以取到1，但爲了答案最優，只取了0，那麼這一位就可以填1，結果也就有1

下面就該求退位的個數了，可以發現，退位的節點數量正好等於1～n安按位建成的trie樹右方孔子樹，

　　當第一次遇到n在第i位爲0是，之前不存在退位現象，而這一爲之後，有(1<<i)個數退位，

　　而當第i爲處理往後，i--，空子樹的一半可能在本層填滿，而表示節點樹減半。

剩下的問題就自己yy了。

 

 

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>#include<stack>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 1100#define MAXV MAXN*2#define MAXE MAXV*200#define MAXT MAXN * 20#define PROB "expxor"typedef long long qword;qword n;double p;qword tot[MAXN];inline qword lowbit (qword x){        return x&(-x);}void print_ldouble(double x){        int t=0;        if (x==0)        {                printf("0.00000000 0");                return ;        }        while (x>=10)        {                x/=10;                t++;        }        while (x<1)        {                x*=10;                t--;        }        printf("%.8lf %d\n",x,t);}void search1(qword n,int lev=62){        if (lev==0)        {                tot[lev]+=n;                return ;        }        if (n&(1LL<<lev))        {                tot[lev]+=n-(1LL<<lev)+1;                for (int i=0;i<lev;i++)                {                        tot[i]+=1LL<<lev>>1;                }                search1(n-(1LL<<lev),lev-1);        }else search1(n,lev-1);}long double work1(qword n){        long double ret=0;        int i;        search1(n);        for (i=63;i>=0;i--)        {                ret+=(long double)(1LL<<i)*tot[i]*(n+1-tot[i]);        }        return 2.0*ret/(n+1)/(n+1);}long double work2(qword n){                        int i;        long double ans=0;        qword tot=0;        for (i=62;!(n&(1ll<<i)) && i>=0;i--);        for (;i>=0;i--)        {                if (n&(1ll<<i))                {                        ans+=(long double)(1ll<<i)*(n+1);                        tot>>=1;                }else                {                        ans+=(long double)(1ll<<i)*(n+1-(tot>>1)-(1ll<<i));                        tot+=(long double)(1ll<<i);                }        }        /*本函數中tot>>=1意思是對於上一層空着的子樹，在本層有一半仍是空的，另一半半滿，可能會加上(1ll<<i)        */        return 1.0*ans/(n+1);}int main(){        freopen(PROB".in","r",stdin);        //        freopen(PROB".out","w",stdout);        qword i,j,k;        qword x,y,z;        qword mx;        scanf(LL "%lf",&n,&p);        double ans=0;        long double p1=1.0/n;        long double p2=1.0/n/n;        ans=work2(n-1)*p+work1(n-1)*(1-p);        print_ldouble(ans);    //    printf("%.8lf\n",ans);        return 0;}