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之和。這個問題確實不太好想，我們先要瞭解如下幾點：
在同類題目中，都有高位完全優先的性質，即只要高位能取到最優解，其他位置完全不用考慮。
如果處理整個數字沒有思路，可以嘗試安慰分解，對於每一位單獨處理。
在本題中，就運用了以上兩點，我們從最高非零位向下枚舉，
如果n的這一位爲1，那麼對於1～n所有數，其最大異或結果這一位一定爲1
如果這一位爲0，那麼如果前面不存在退位現象，即本可以取到1，但爲了答案最優，只取了0，那麼這一位就可以填1，結果也就有1
下面就該求退位的個數了，可以發現，退位的節點數量正好等於1～n安按位建成的trie樹右方孔子樹，
當第一次遇到n在第i位爲0是，之前不存在退位現象，而這一爲之後，有(1[i)個數退位，
而當第i爲處理往後，i--，空子樹的一半可能在本層填滿，而表示節點樹減半。
剩下的問題就自己yy了。
#include
#include
#include
#include
#include
#include
#include
#include[span style="color: rgba(0, 0, 255, 1)">set
#include
#include
#include[span style="color: rgba(0, 0, 255, 1)">string
#include
#include
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 1100
#define MAXV MAXN2
#define MAXE MAXV200
#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[span style="color: rgba(128, 0, 128, 1)">1)
{
x=10;
t--;
}
printf("%.8lf %d\n",x,t);
}//代码效果参考：http://www.ezhiqi.com/zx/art_3026.html
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
{
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】);
}//代码效果参考：http://www.ezhiqi.com/bx/art_2971.html
return 2.0ret/(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.0ans/(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;
}
by mhy12345() 未经允许请勿转载
本博客已停用，新博客地址：
