codeforces 2081A 题解

前言

这道题和之前这道题有很多共同之处。相比之下，这道题可能更深刻一点。

题意

对于一个二进制数，有两个操作

除以二向上取整
除以二向下取整

进行每种操作的概率为1/2，经过若干次操作后将这个数字变为1，求出操作的长度的期望

思路

乍一看很像数学题，求数学期望之类的，但结合上一题的结论，可以注意到这个操作的长度只能为n或n-1，当且仅当数字在第最低位发生进位时答案为n

那么这道题可以转化为求第i位发生进位的概率。

显然从低到高第i位发生进位的概率仅与第i位的数值和第i-1位发生进位的概率有关，记第i位发生进位的概率为f(i)具体来说：

若第i位为0，那么只有当第i-1位发生进位时第i位有可能发生进位，且$f(i) = \frac{1}{2}f(i - 1)$
若第i位为1，那么$f(i) = \frac{1}{2}f(i - 1) + \frac{1}{2}$

本题计算除法时除数总为2，所以只需要预处理inv2即可，不需要写逆元函数。

#include <bits/stdc++.h>

using namespace std;

const int inv2 = 500000004;
const int MOD = 1e9 + 7;
int n;
string s;
void solve() {
    cin >> n >> s;
    s = " " + s;
    int f = 0;
    for(int i = n; i > 1; --i) {
        f = inv2 * 1ll * (f + s[i] - '0') % MOD; 
    }

    cout << n - 1 + f << endl;
}
int main() {
    int t;  cin >> t;
    while(t--) {
        solve();
    }
}

后记

代码其实还是比较简单的，但是其实思维量比想象的大，所以rating为1800啊