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