2017 ACM-ICPC 亚洲区（西安赛区）网络赛 B. Coin
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})pq(pq≤21).
The question is, when Bob tosses the coin kk times, what's the probability that the frequency of the coin facing up is even number.
If the answer is \frac{X}{Y}YX, because the answer could be extremely large, you only need to print (X * Y^{-1}) \mod (10^9+7)(X∗Y−1)mod(109+7).
Input Format
First line an integer TT, indicates the number of test cases (T \le 100T≤100).
Then Each line has 33 integer p,q,k(1\le p,q,k \le 10^7)p,q,k(1≤p,q,k≤107) indicates the i-th test case.
Output Format
For each test case, print an integer in a single line indicates the answer.
2 1 1
3 1 2
样例输出
500000004
555555560
题目意思是说Bob丢硬币，这个硬币比较特殊，正面朝上的概率不是1/2，而是q/p
现在问Bob丢k次以后，正面朝上次数是偶数次的概率。
（一开始队友把Even读成奇数，怎么样都对不上样例）
(╯' - ')╯︵ ┻━┻ (掀桌子)
┬─┬ ノ( ' - 'ノ) {摆好摆好)
(╯°Д°)╯︵（再掀一次）
后来打个表，打1/9—8/9Mod(1e9+7).，最后发现5/9的时候是答案。
我才恍然发现Even是偶数的意思，Odd是奇数的意思。还好没坑太久
那么这道题目就变成了一个求概率的问题。
很容易得到一个公式P=C（k，n）* p^n *(1-p)^(k-n);
N的值从0-最大小于K的偶数。这样我们只需要求和就可以。
分母恒为p^n，但这个式子中的分子组合数太大，简单处理必然有问题。
我们把这个式子展开，设每一项为D1,+D2+D3+D4…Dn=1;
现在进行变形，令a为-a，那么上式展开后就变成D1-D2+D3-D4…+Dn=（一个可以求的值）
把这两个式子相加除以二就可以求得偶数项的求和值，就是我们要的答案。
上面说的可以求的值就是 （ 【(p-2q)/p】^n+1）/2；
不太会用公式编译器，大家将就这看吧。
最后值得说的是，最后这道题目还是那个看错题目的队友AC的。 (๑•̀ㅂ•́) ✧
The question is, when Bob tosses the coin kk times, what's the probability that the frequency of the coin facing up is even number.
If the answer is \frac{X}{Y}YX, because the answer could be extremely large, you only need to print (X * Y^{-1}) \mod (10^9+7)(X∗Y−1)mod(109+7).
Input Format
First line an integer TT, indicates the number of test cases (T \le 100T≤100).
Then Each line has 33 integer p,q,k(1\le p,q,k \le 10^7)p,q,k(1≤p,q,k≤107) indicates the i-th test case.
Output Format
For each test case, print an integer in a single line indicates the answer.
样例输入
22 1 1
3 1 2
样例输出
500000004
555555560
题目意思是说Bob丢硬币，这个硬币比较特殊，正面朝上的概率不是1/2，而是q/p
现在问Bob丢k次以后，正面朝上次数是偶数次的概率。
（一开始队友把Even读成奇数，怎么样都对不上样例）
(╯' - ')╯︵ ┻━┻ (掀桌子)
┬─┬ ノ( ' - 'ノ) {摆好摆好)
(╯°Д°)╯︵（再掀一次）
后来打个表，打1/9—8/9Mod(1e9+7).，最后发现5/9的时候是答案。
我才恍然发现Even是偶数的意思，Odd是奇数的意思。还好没坑太久
那么这道题目就变成了一个求概率的问题。
很容易得到一个公式P=C（k，n）* p^n *(1-p)^(k-n);
N的值从0-最大小于K的偶数。这样我们只需要求和就可以。
分母恒为p^n，但这个式子中的分子组合数太大，简单处理必然有问题。
现在我们需要用到一个概率与数理统计里面的公式
我们把这个式子展开，设每一项为D1,+D2+D3+D4…Dn=1;
现在进行变形，令a为-a，那么上式展开后就变成D1-D2+D3-D4…+Dn=（一个可以求的值）
把这两个式子相加除以二就可以求得偶数项的求和值，就是我们要的答案。
上面说的可以求的值就是 （ 【(p-2q)/p】^n+1）/2；
不太会用公式编译器，大家将就这看吧。
最后值得说的是，最后这道题目还是那个看错题目的队友AC的。 (๑•̀ㅂ•́) ✧
如果看不懂，可以在评论区留言，近期会尽快回复
#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;
}
