题目描述

最近，scx 写了一个奇怪的程序，伪代码如下：

//input: integers x, k, p
a = x;
for(step = 1; step <= k; step = step + 1){
    rnd = [random integer from 1 to 100];
    if(rnd <= p)
        a = a * 2;
    else
        a = a + 1;
}

s = 0;

while(remainder after dividing a by 2 equals 0){
    a = a / 2;
    s = s + 1;
}

现在 scx 想知道，给定 $x, k, p$，求变量 $s$ 的期望值。

输入格式

输入共一行，包含三个正整数 $x, k, p$ ($1 \leq x \leq 10^9, 1 \leq k \leq 200, 0 \leq p \leq 100$)。

输出格式

输出变量 $s$ 的期望值，绝对误差或相对误差不超过 $10^{-6}$。

题解

记 $f_{i, j}$ 为原始的 $a$ (即 $x$) 经过 $i$ 次外层循环后，$a$ 再加上 $j$，所得的变量 $s$ (ctz，后缀 0 计数) 的期望值，则有 $f_{0, j} = \mathrm{ctz}(x + j)$，其中 ctz(x) 为后缀 0 计数函数，原型为 __builtin_ctz(x)。

再记 $p$ 为 $\times 2$ 的概率 (= (double)p * 0.01))，$q = 1 - p$ 位 $+ 1$ 的概率。

考虑转移，若 $j$ 为奇数，则第 $i$ 次的结果为 $\times 2$ 就无意义了，所以只能由第 $i$ 次的结果为 $+ 1$ 转移过来，即

$$ f_{i, j} = f_{i-1, j+1} \cdot q $$

若 $j$ 为偶数，则第 $i$ 次不仅可以 $+ 1$，还可以是 $\times 2$。由于是乘 $2$ 后再加上 $j$，相当于加上 $\dfrac j2$ 后再乘 $2$，因此 $j$ 为偶数的转移是

$$ f_{i, j} = f_{i-1, j+1} \cdot q + \left( f_{i-1, j/2} + 1 \right) \cdot p $$

总转移为：

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

由于真正有影响的不超过 $256$，所以第二维可以只算到 $O(k)$。

答案当然就是 $f_{k, 0}$，时间复杂度 $O(k^2)$，轻松水过。

代码

#include <bits/stdc++.h>
#define K 544
using namespace std;

int x, k, i, j;
double p, q, f[K][K];

int main(){
    scanf("%d%d%d", &x, &k, &i);
    p = (double)i * 0.01; q = 1.0 - p;
    memset(f, 0, sizeof f);
    for(j = 0; j <= k; ++j) f[0][j] = (double)__builtin_ctz(x + j);
    for(i = 1; i <= k; ++i)
        for(j = 0; j <= k; ++j){
            f[i][j] += f[i - 1][j + 1] * q;
            f[i][j << 1] += (f[i - 1][j] + 1.0) * p;
        }
    printf("%.15lf\n", f[k][0]);
    return 0;
}

坑

坑1：初始化的时候，不要忘记 $0$，就是说对 $0 \leq j \leq k$，有 $f_{0, j} = \mathrm{ctz}(x + j)$。

坑2：然后就是 $+ 1$ 和 $- 1$ 搞清楚，还有 $\times 2$ 和 $\div 2$，由于后者只在 $j$ 为偶数时转移，因此可以直接从 $f_{i-1, j}$ 转移到 $f_{i, 2j}$。