计蒜客 2017 ACM-ICPC 亚洲区(西安赛区)网络赛 B coin(求乘法逆元)

148 阅读 0 评论 98 点赞

我是靠谱客的博主悦耳咖啡，这篇文章主要介绍计蒜客 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 $qp(qp≤12)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 $XYfrac{X}{Y}$ , because the answer could be extremely large, you only need to print $X * Y^{-1}) mod (10^9+7)$ .

Input Format

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

Then Each line has $3$ integer $10^7)$ indicates the i-th test case.

Output Format

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

样例输入

复制代码

样例输出

复制代码

题目来源

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

题意:

计算扔k次硬币，正面朝上的次数为偶数的概率。再将答案mod(1e9+7)

解析:

正面朝上概率为a，反面朝上概率为b

a+b=1；

ans=C(k,0)*a^0*b^k+C(k,2)*a^2*b^(k-2)+...

(a+b)^k= C(k,0)*a^0 *b^k+ C(k,1)*a^1*b^(k-1) +C(k,2)*a^2*b^(k-2) .......+C(k,k)*a^k*b^0
(b-a)^k= C(k,0) *(-a)^0 *b^k +C(k,1)*(-a)* b^(k-1) .........+C(k,k)*(-a)^k*b^0

可得ans=((a+b)^k+(b-a)^k)/2 再将a=p/q,b=(1-p/q)带入

得(（p^k）+(p-2q)^k)/(2*p^k)

除法的模运算就是求乘法逆元

x*(x^-1)=1(mod p) 乘法逆元性质

d=(x/y)(mod p) => y*d=x(mod p) => y*y^-1*d=x*y^-1(mod p) => d=x*y^-1(mod p)

求乘法逆元的三种方法

http://blog.csdn.net/rain722/article/details/53170288

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long int N = 1e9+7;
long long p,q,k;
long long zi,mu;
long long quickmulti(long long a,long long b)
{
long long ans=1;
while(b)
{
if(b&1) ans = ((ans%N)*(a%N)) % N;
a = ((a%N)*(a%N)) % N;
b=b>>1;
}
return ans;
}
long long inv2(long long b)
{
return quickmulti(b,N-2);
}
int main()
{
int t;
long long x,y,d,x0;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&p,&q,&k);
zi=(quickmulti(p,k)+quickmulti(p-2*q,k))%N;
mu=(2*quickmulti(p,k))%N;
long long
ans=(zi*inv2(mu))%N;
printf("%lldn",ans);
}
return 0;
}