这道题一个朴素的思路就是：维护 \(f_{i,j}\) 表示第 \(i\) 轮后 \(x=j\) 的方案数。时间复杂度 \(O(k\times 2^k)\)。显然过不了。
我们尝试寻找一个能抛开 \(x\) 的值域的做法。不妨重新设 \(f_{i,j}\) 表示第 \(i\) 轮结束时的 \(x\)，增加 \(j\) 之后期望的末尾 \(0\) 个数是多少。发现这可以通过枚举第 \(i\) 轮的两种转移方式得到：
-
第 \(i\) 轮的操作是加 \(1\)
\[f_{i,j}\leftarrow f_{i-1,j+1} \] -
第 \(i\) 轮的操作是乘以 \(2\)
\[f_{i,2j}\leftarrow f_{i-1,j} \]
注意这里和常见的 \(\text{DP}\) 略有不同，它这里是通过枚举第 \(i\) 轮的操作来把一种状态转移到另一种等价的状态。
最终答案即为 \(f_{k,0}\)。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 210;
int x, k; double p, f[N][N];
int main(){
scanf("%d%d%lf", &x, &k, &p), p /= 100;
FL(i, 0, k) f[0][i] = __builtin_ctz(x + i);
FL(i, 1, k) FL(j, 0, k){
f[i][j] = f[i - 1][j + 1] * (1 - p);
if(!(j & 1)) f[i][j] += (f[i - 1][j >> 1] + 1) * p;
}
printf("%.12lf", f[k][0]);
return 0;
}