Description
一共执行\(k\)次，每次有\(p\%\)把\(x * 2\)，有\((100 - p)\%\)把\(x + 1\)。问二进制下\(x\)末尾期望\(0\)的个数。
Solution
设\(f[i][j]\)为执行第\(i\)次后\(x + j\)末尾期望\(0\)的个数
加一：$f[i + 1][j - 1] = f[i + 1][j - 1] + (100 - p)% * f[i][j]; $
乘二：\(f[i + 1][j * 2] = f[i + 1][j * 2] + p\% * (f[i][j] + 1);\)
#include<bits/stdc++.h>
using namespace std;
int x, k;
double p, p1;
double f[300][300];
int main() {
scanf("%d%d%lf", &x, &k, &p);
p /= 100, p1 = 1.0 - p;
for (int i = 0; i <= k; i ++)
for (int j = x + i; j % 2 == 0; j /= 2)
f[0][i] ++;
for (int i = 0; i < k; i ++)
for (int j = 0; j <= k; j ++) {
if (j)
f[i + 1][j - 1] += p1 * f[i][j]; // + 1
if (j * 2 <= k)
f[i + 1][j * 2] += p * (f[i][j] + 1); // * 2
}
printf("%.10f\n", f[k][0]);
return 0;
}