原题点 这里

解法思路

1.概率分析：

由于每场比赛是赢（1）或者输（0），我们需要计算 00111 这个子序列在长度为 n 的比赛结果中出现的期望次数。比赛胜利的概率为 p = a / b，失败的概率为 1 - p = (b - a) / b。
我们可以将这个问题转化为概率计算：找到所有满足模式“00111”的子串出现的概率。

2.期望的计算：

设某个子串从第 i 到第 i+4 为 “00111”，我们需要这个子串具体的概率为：
Pr(00111)=(1−p)⋅(1−p)⋅p⋅p⋅p
因此该概率可以计算为：
Pr(00111)=((b-a)/b)^2 * (a/b)^3

3.高效计算
在这道题目中，由于 n 可以高达 100,000，我们不能暴力遍历所有可能的子序列，因此我们需要找到一种高效计算的方法。
模逆元是解决有理数在模数下计算的关键，我们可以通过扩展欧几里得算法来计算模逆元，从而得到分数在模数下的表示。

4.结果的期望：

每个位置都有可能是子串 “00111” 的起始位置，因此期望的子串个数为：
期望值 = (n-4) * Pr(00111)

复杂度分析
每个测试用例的复杂度为 O(log b)，因为主要计算在于模逆元和快速幂。
总体复杂度为 O(T log b)，其中 T 为测试用例的数量，最大为1e5，b 最大为 1e4。

代码实现

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

// 快速幂求解 a^b % mod
long long mod_pow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 求模逆元
long long mod_inv(long long a, long long mod) {
    return mod_pow(a, mod - 2, mod);  // 费马小定理
}

void solve()
{
    long long a, b, n;
    cin >> a >> b >> n;

    if (n < 5) {
        cout << 0 << '\n';
        return;
    }

    // 计算 p=a/b 和 (1-p)=(b-a)/b 的模逆元
    long long p = a * mod_inv(b, MOD) % MOD;         // p = a/b, 即 p=a*b'(mod MOD)
    long long q = (b - a) * mod_inv(b, MOD) % MOD;   // q = (b-a)/b, 即p=(b-a)*b'(mod MOD)

    // 计算 Pr(00111) = q^2 * p^3 % MOD
    long long prob = q * q % MOD * p % MOD * p % MOD * p % MOD;

    // 期望值为 (n - 4) * Pr(00111) % MOD
    long long res = (n - 4) * prob % MOD;

    cout << res << '\n';
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}