首先看到 \(\times 2\) \(+1\) 和最后答案的计算方式，能想到看成二进制来处理。
考虑到 \(\times 2\) 就是在最后加了一个 \(0\)。
不妨倒过来看，\(\times 2\) 就相当于舍弃了最低位。
于是可以考虑 \(\text{DP}\)，\(f_{i, j}\) 为考虑后面的 \(i\) 个操作，目前 \(+\) 的值为 \(j\) 的概率。
那么如果上一步选择 \(+1\)，概率就为 \(f_{i - 1, j - 1}\times (1 - p)\)。
如果上一步是 \(\times 2\)，就需要看最后一位是 \(0\) 还是 \(1\)，似乎不好处理最后的答案。
但是因为如果舍弃的最后一位为 \(1\)，后面末尾的 \(0\) 就一定不会算上贡献。
于是进一步完善 \(\text{DP}\) 状态的含义：记 \(f_{i, j}\) 为考虑后 \(i\) 个操作加的值为 \(j\) 且目前舍弃掉的位都保证为 \(0\) 的方案数。
首先 \(+1\) 的转移是不变的，\(f_{i - 1, j - 1}\times (1 - p)\)。
\(\times 2\) 就只需要考虑末尾为 \(0\) 的情况转移过来，贡献为 \(f_{i - 1, 2j}\times p\)。
同时因为这一位舍弃的 \(0\) 一定能记入答案，考虑直接把这部分贡献提前记入答案。
对于 \(f_{k, i}\)，相当于到最后还剩了 \(+ i\)，便还有的贡献为 \(f_{k, i}\times \operatorname{calc}(x + i)\)，\(\operatorname{calc}(x)\) 为 \(x\) 末尾连续的 \(0\) 的个数。
时间复杂度 \(O(k^2)\)。
#include<bits/stdc++.h>
using f128 = long double;
const int maxk = 2e2 + 10;
int calc(int w) {
int tot = 0;
while (~ w & 1) w >>= 1, tot++;
return tot;
}
f128 f[maxk][maxk * 2];
int main() {
int x, k; f128 p; scanf("%d%d%Lf", &x, &k, &p);
p /= 100;
f[0][0] = 1;
f128 ans = 0;
for (int i = 1; i <= k; i++)
for (int j = 0; j <= k; j++) {
if (j) f[i][j] += f[i - 1][j - 1] * (1 - p);
f[i][j] += f[i - 1][j * 2] * p, ans += f[i - 1][j * 2] * p;
}
for (int i = 0; i <= k; i++) ans += f[k][i] * calc(x + i);
printf("%.10Lf\n", ans);
return 0;
}