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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
#define rep0(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define rep_0(i, n) for (int i = n - 1; i >= 0; i--)
#define rep_1(i, n) for (int i = n; i > 0; i--)
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define mem(x, y) memset(x, y, sizeof(x))
/**
题目大意
给出抛硬币正面朝上的概率为q/p
求抛k次偶数次正面朝上的概率
思路
Σ C(i, k) * (q / p)^i * (1 - q / p)^(k - i)
(i = 0, 2, 4...)
x = Σ C(i, k) * a^i * b^(k - i)
(i = 0, 1, 2, 3...)
y = Σ C(i, k) * (-a)^i * b^(k - i)
(i = 0, 1, 2, 3...)
(x + y) / 2 即为所求：
(1 + (p - 2 * q)^k / p^k) / 2
=
(p^k + (p - 2 * q)^k) / (2 * p^k)
除法取模
设分子为i 分母为j
i / j % MOD = x
法1: 扩展欧几里得
j * x = i(mod MOD)
法2: i / j % MOD <=> i * j^(-1) (j^(-1) 为j的逆元)
由费马小定理，MOD为质数，且与j互质
j^(MOD - 1) = 1(mod MOD)
j * j^(MOD - 2) = 1(mod MOD)
则j^(MOD - 2)为j的逆元
*/
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
LL r = exgcd(b, a % b, x, y);
LL temp = x;
x = y;
y = temp - a / b * y;
return r;
}
LL multi(LL a, LL b)
{
LL ans = 1;
while (b)
{
if (b & 1)
ans = (ans * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
int t, p, q, k;
LL ans;
scanf("%d", &t);
while (t--)
{
scanf("%d %d %d", &p, &q, &k);
LL a, b = MOD, x, y, p_k = multi(p, k);
a = (p_k + multi(p - 2 * q, k)) % MOD;
b = 2 * p_k % MOD;
ans = a * multi(b, MOD - 2) % MOD;
/**
a = 2 * p_k % MOD;
exgcd(a, b, x, y);
LL temp = (p_k + multi(p - 2 * q, k)) % MOD;
ans = ((x % MOD + MOD) % MOD * temp) % MOD;
*/
printf("%lldn", ans);
}
return 0;
}

最后

以上就是爱撒娇耳机为你收集整理的2017 ACM-ICPC 亚洲区（西安赛区）网络赛_Coin的全部内容，希望文章能够帮你解决2017 ACM-ICPC 亚洲区（西安赛区）网络赛_Coin所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。