思路与算法

用尾和E[v2(w)]=Σ_{k≥1}Pr(2^k整除w)。令F_s(k,j)为s步后w≡−j (mod2^k)的概率，F_0由初值判定。反推最后一步：加1变成F_{s−1}(k,j+1)；倍增只有j偶数可行，变成F_{s−1}(k−1,j/2)。按概率加权，k0恒为1。j最多n，k取到n+31足够，用滚动数组。

正确性说明

正整数v2的尾和恒等式成立。加1与倍增的逆同余条件分别如上，两个操作互斥且概率固定，故全概率公式给出准确转移。初始F0为真实整除指示，归纳得全部概率。任一步仅加1或倍增，最终w≤(x+n)2^n<2^(n+30)，所以更高整除事件概率0，有限求和精确。

复杂度

K=n+31，初始化O(Kn)，每层有效j至多n−s+1，时间O(Kn²)，滚动空间O(Kn)。n0时直接由初始化求尾和。

易错点

本地公开勘误为倍增2x，不能按原笔误x/2产生0。j奇数时倍增分支为0；k0是概率1而非整除运算。p0/p100和n0均合法，输出按1e−6绝对误差比较。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using D = long double;
int main() {
    int x, n, p;
    cin >> x >> n >> p;
    int K = n + 31, W = n + 1;
    vector<D> a((K + 1) * W), b(a.size());
    for (int k = 0; k <= K; k++)
        for (int j = 0; j <= n; j++)
            a[k * W + j] = (k == 0 || (k <= 30 && ((x + j) % (1LL << k) == 0)));
    D prob = p / 100.0L;
    for (int s = 1; s <= n; s++) {
        fill(b.begin(), b.end(), 0);
        for (int j = 0; j <= n - s; j++)
            b[j] = 1;
        for (int k = 1; k <= K; k++)
            for (int j = 0; j <= n - s; j++)
                b[k * W + j] = (1 - prob) * a[k * W + j + 1] +
                               (j % 2 == 0 ? prob * a[(k - 1) * W + j / 2] : 0);
        a.swap(b);
    }
    D ans = 0;
    for (int k = 1; k <= K; k++)
        ans += a[k * W];
    cout << fixed << setprecision(10) << ans << '\n';
}