- CF 441E http://codeforces.com/contest/441/problem/E
- 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;
- }
来源: http://www.bubuko.com/infodetail-3038741.html