Description：

对 $ x$ 执行 $ n $ 次操作，每次操作有 $ p\% $ 的概率令 $ x = x \times 2$ ， $(100 − p)\% $ 的概率令 $ x = x + 1$ 。假设最后得到的值为 $ w$ ，求 $w $ 的质因数分解中 $ 2 $ 的次数的期望。

$1\le n \le 200$

Solution：

发现只有 $200$ 个操作，而 $2^8=256$ ，也就是说最多会向第九位进一次位，那么一个想法是可以把后 $8$ 位压起来，对于向第 $9$ 位进位的问题，发现如果第 $9$ 位前面有很多一，那么进一位会把这些连续的一都变成 $0$ ，于是状态里还要记一个第九位的值和第九位及之前和第九位相同的连续的数的长度为几，即 $f[opt\_th][ninth\_num][ninth\_len][last\_8\_bits]$ 。转移时分情况讨论一下就行了，最后统计答案也很好办，但要注意后八位都为零时能否和第九位及之前的连起来。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n;

double p;

int x;

#define MAXN 250

double f[MAXN][2][MAXN][256];

int lowbit(int x){return x & (-x);}

int main()

{

	freopen("exp.in","r",stdin);

	freopen("exp.out","w",stdout);

	cin >> x >> n >> p;

	p /= 100;

	int cur = 0;

	int l = 0;

	while(((x >> (8 + l)) & 1) == ((x >> 8) & 1))++l;

	f[0][(x >> 8) & 1][l][x & ((1 << 8) - 1)] = 1;

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

	{

		cur = cur ^ 1;

		for(int t = 0;t <= 1;++t)

		{

			for(int l = 1;l <= 233;++l)

			{

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

				{

					if(s != ((1 << 8) - 1))f[i][t][l][s + 1] += f[i - 1][t][l][s] * (1 - p);

					else

						if(t == 1)f[i][0][l][0] += f[i - 1][1][l][s] * (1 - p);

						else f[i][1][1][0] += f[i - 1][t][l][s] * (1 - p);

					if(t == ((s >> 7) & 1))f[i][t][l + 1][(s << 1) & ((1 << 8) - 1)] += f[i - 1][t][l][s] * p;

					else f[i][((s >> 7) & 1)][1][(s << 1) & ((1 << 8) - 1)] += f[i - 1][t][l][s] * p;

				}

			}

		}

	}

	double ans = 0;

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

		for(int k = 1;k <= 233;++k)

			for(int h = 0;h <= (1 << 8) - 1;++h)

				if(f[n][j][k][h] != 0) 

					if(h != 0)

						ans += f[n][j][k][h] * log2(lowbit(h));

					else

						if(j == 0)ans += f[n][j][k][h] * (k + 8);

						else ans += f[n][j][k][h] * 8;

	printf("%.10lf\n",ans);

	fclose(stdin);

	fclose(stdout);

	return 0;

}