2017 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})$ .

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

题目来源

2017 ACM-ICPC 亚洲区（西安赛区）网络赛

【题解】

一道数学题，要结果的逆元，不过要先推公式，推出来再用二项式定理化简，就能写了。

【AC代码】

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<cmath>
#include<vector>using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;#define pi acos(-1.0)
#define eps 1e-10
#define pf printf
#define sf scanf
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define e tree[rt]
#define _s second
#define _f first
#define all(x) (x).begin,(x).end
#define mem(i,a) memset(i,a,sizeof i)
#define for0(i,a) for(int (i)=0;(i)<(a);(i)++)
#define for1(i,a) for(int (i)=1;(i)<=(a);(i)++)
#define mi ((l+r)>>1)
#define sqr(x) ((x)*(x))const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int t;
ll p,q,k;ll quick(ll x,ll y)
{ll ans=1;while(y){if(y&1)ans=ans*x%mod;y>>=1;x=x*x%mod;}return ans;
}ll fact(ll x,ll y)
{ll ans=1;for(int i=x,j=1;j<=y;j++,i--)ans*=i;for(int i=1;i<=y;i++)ans/=i;return ans;
}void solve()
{ll ans=0;ll o=0,y;for(int i=0;i<=k;i+=2){o+=fact(k,i)*quick(p-q,k-i)*quick(q,i);}y=quick(p,k);pf("%lld   %lld\n",o,y);
}int main()
{sf("%d",&t);while(t--){sf("%lld%lld%lld",&p,&q,&k);
//        ll x=p>>1;
//        ll y=p/2-q;ll t1=quick(p,k);ll t2=quick(p-2*q,k);ll u=quick(2,mod-2);//注意不能直接除ll t3=((t1+t2)%mod)*u%mod;ll r=quick(p,k);ll ans=t3*quick(r,mod-2)%mod;pf("%lld\n",ans);}return 0;
}