HZOJ 简单的期望

性质：一个数分解质因数后2的次数=二进制下末尾连续0的个数。

乘2比较好考虑，比较恶心的是+1。一个$k*2^0$的数+1后可能会出现很多情况。但是k这个数表示不出来。

但是加的操作最多有200次，也就是说最多影响二进制下的后8位。根据上述性质，我们把后8为作为状态，统计概率。

但是只有后8位状态的的话还是不可做，再加上第9位状态以及与第九位相同的连续长度来考虑进位。

即f[i][j][s][k]表示i次操作后，后8位为s，第九位为k，有连续j位的概率。

转移少麻烦但还是比较好想的。本题难度在于状态定义。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<bitset>

#define int LL

#define LL long long

using namespace std;

int x,n,p;

double gl1,gl2;

double f[210][255][1<<10][2];

int cnt[1<<10];

signed main()

{

//	freopen("in.txt","r",stdin);

//	freopen("1.out","w",stdout);

	cin>>x>>n>>p;

	gl1=p/100.0,gl2=(100-p)/100.0;

	int num=0;

	for(int j=0;(((1<<j)&x)==0);j++)num++;

	f[0][num>8?num-8:1][x&((1<<8)-1)][(bool)(x&(1<<8))]=1;

//	cout<<(num>8?num-8:1)<<" "<<(x&((1<<8)-1))<<" "<<(x&(1<<8))<<endl;

	for(int i=0;i<n;i++)

		for(int j=1;j<=250;j++)

		for(int s=0;s<(1<<8);s++)

		{

			if(s!=(1<<8)-1)f[i+1][j][s+1][0]+=f[i][j][s][0]*gl2;

			else		   f[i+1][1][0][1]  +=f[i][j][s][0]*gl2;

			if(s!=(1<<8)-1)f[i+1][j][s+1][1]+=f[i][j][s][1]*gl2;

			else		   f[i+1][j][0][0]  +=f[i][j][s][1]*gl2;

			bool maxn=s&(1<<7);

			f[i+1][maxn==0?j+1:1][(s<<1)&((1<<8)-1)][maxn]+=f[i][j][s][0]*gl1;

			f[i+1][maxn==1?j+1:1][(s<<1)&((1<<8)-1)][maxn]+=f[i][j][s][1]*gl1;

		}

/*	for(int i=0;i<n;i++)

		for(int j=1;j<=10;j++)

			for(int s=0;s<(1<<8);s++)

				cout<<f[i][j][s][0]<<" "<<f[i][j][s][1]<<endl*/

	for(int i=0;i<(1<<8);i++)

		for(int j=0;j<=8&&(((1<<j)&i)==0);j++)cnt[i]++;

	double ans=0;

	for(int i=1;i<(1<<8);i++)

		for(int j=1;j<=250;j++)

			ans+=(f[n][j][i][0]+f[n][j][i][1])*cnt[i];

	for(int j=1;j<=250;j++)ans+=f[n][j][0][0]*(j+8)+f[n][j][0][1]*8;

	printf("%0.10lf\n",ans);

}

巴特西

HZOJ 简单的期望

最新文章

热门文章