CF441E Valera and Number 题解

题目链接：CF441E Valera and Number

题意：

给出一个数 $x$，对它进行 $k$ 次操作，每次操作：

• 以 $p \%$ 的概率对它乘以 $2$。
• 以 $(100 - p) \%$ 的概率对它加上 $1$。

求该数最终二进制下末尾 $0$ 个数的期望。

输入格式：

The first line of the input contains three integers $x,k,p(1\le x\le 10^{9}, 1\le k\le 200, 0\le p\le 100)$ .

输出格式：

Print the required expected value. Your answer will be considered correct if the absolute or relative error doesn’t exceed $10^{-6}$ .

设 $f_{i,j}$ 表示 $x$ 经过执行过 $i$ 次后， $x+j$ 的期望答案，则

$$f_{0,j} = \mathrm{ctz}(x+j) \\[6pt] f_{i, j}=f_{i-1, j+1} \cdot q+[2 \mid j]\left(f_{i-1, j / 2}+1\right) \cdot p$$

最后答案就是 $f_{k,0}$ 。说实话这个转移的前一部分还是有点晕的，我想了好一会。

分析下复杂度。考虑 dp 中一条贡献路径的 $j$ ，显然贡献的过程会使 $j$ 乘 $2$ 或者加 $1$ 。

而当 $j > k$ 时，减 $1$ 操作是不可能使得 $j=0$ 的，因为至多 $k$ 次操作，因此这样的 $j$ 对答案没有贡献

综上，时间复杂度 $\mathcal{O}(k^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(555))

int x,k,t;
double p,q,f[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(15);
    cin >> x >> k >> t; p = t * 0.01; q = 1.0 - p;
    for(int j = 0; j <= k; j++) f[0][j] = (double)(__builtin_ctz(x + j));
    for(int i = 1; i <= k; i++)
        for(int j = 0; j <= k; j++)
        {
            f[i][j] += f[i - 1][j + 1] * q;
            f[i][j << 1] += (f[i - 1][j] + 1) * p;
        }
    cout << f[k][0] << '\n';
    return 0;
}

---

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/cf441E.html

[2] https://www.luogu.com.cn/blog/dowhiletrue/solution-cf441e