牛客等级之题N1（8.3场）题解

基础期望练习题。

考虑设 表示第 ***作后剩余黑球期望个数。令 ，，根据期望的线性性，则有：

因为每次操作的时候，有 的概率加入一个黑球，加上第 轮期望剩下 个黑球，则现在期望剩下 个黑球。

然后考虑扔掉一个球后，每个黑球都有 的概率被留下，所以期望剩下 个黑球。

得到递推式之后，我们可以得到如下两个做法：

迭代法：

注意到答案为 ，则所求即为： 。

组合意义法

考虑上面所述的组合意义，注意到每个球如果经历过 次操作的第 步，则最后有 的概率被留下来。

则不难得到：

部分代码：

const int mod = 1e9 + 7;

inline int fsp(int x, int k = mod - 2) {
    int s = 1;
    while(k) {
        if(k & 1) s = 1LL * s * x % mod;
        x = 1LL * x * x % mod, k >>= 1;
    } return s;
}

int main() {
    int n, m, k, a, b;
    cin >> n >> m >> k >> a >> b;
    int p = 1LL * a * fsp(b) % mod;
    int q = 1LL * (n + m) * fsp(n + m + 1) % mod;
    int pw = fsp(q, k), iv = 1LL * (pw - 1) * fsp(q - 1) % mod;
    cout << (1LL * pw * n + 1LL * p * iv % mod * q) % mod << endl;
    return 0;
}