GroupBlog

Bob has a not even coin, every time he tosses the coin, the probability that the coin's front face up is $\frac{q}{p}(\frac{q}{p} \le \frac{1}{2})$ .

The question is, when Bob tosses the coin $k$ times, what's the probability that the frequency of the coin facing up is even number.

If the answer is $\frac{X}{Y}$ , because the answer could be extremely large, you only need to print $Y^{-1}) \mod (10^9+7)$ .

Input Format

First line an integer $T$ , indicates the number of test cases ( $\le 100$ ).

Then Each line has $3$ integer $p,q,k(1\le p,q,k \le 10^7)$ indicates the i-th test case.

Output Format

For each test case, print an integer in a single line indicates the answer.

样例输入

2
2 1 1
3 1 2

样例输出

500000004
555555560

题目题意:题目给了一种特殊的硬币，其中正面朝上的概率是q/p,我们丢硬币k次，问硬币朝上的次数是偶数的概率为多少（要 mod 1e9+7)

题目分析:根据题目题意不难推出答案为

C (k,a)*(q/p)^a*(1-q/p)^(k-a) mod 1e9+7 (其中a是0 2 4 ..这些偶数)

这里我们先用一个公式

发现我们的答案和这个式子有点像，只是一个遍历所有的数（0到n) 一个是(0,2,4都是偶数)

怎么办了？

我们来看一下下面例子:
a1+a2+a3+a4+a5+...+an

假如我们要求a1+a3+a5+.....

只要我们知道 a1-a2+a3-a4+a5-a6+..-..

那么答案就是原式加上它除以2

现在我们知道原始了，其中p=(q/p),q=(1-q/p)

那么p+q=1

不难发现我们只需要将p令为-p展开就可以得到了

那么即(-p+q)=(p-2*q)/p

那么答案即为

然后就可以算了，费马小定理求逆元

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;

const ll  mod=1e9+7;

ll fast_pow(ll base,ll k)
{
    ll ans=1;
    while (k) {
        if (k&1)
          ans=ans*base%mod;
        base=base*base%mod;
        k>>=1;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--) {
        ll p,q,k;
        scanf("%lld%lld%lld",&p,&q,&k);
        ll ans=(p-2*q)*fast_pow(p,mod-2)%mod;
        ans=fast_pow(ans,k);
        ans=ans+1;
        ans=(ans%mod+mod)%mod;//注意这里处理一下，避免为负数
        ans=ans%mod*fast_pow(2,mod-2)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}