题解-LibreOJ-6513「雅礼集训 2018 Day10」足球大战

足球比赛共 $n$ 秒中，主队每秒进球概率为 $p$，客队每秒进球概率为 $q$，求主队获胜概率。

$n \le 10000000$

记 $f(i,j)$ 表示 $n$ 秒种后，主队进 $i$ 个球，客队进 $j$ 个球的概率。则有：
$$
f(i,j)={n \choose i}\times p^i\times (1-p)^{n-i} \times {n\choose j}\times q^j \times (1-q)^{n-j}
$$
要使得 $i>j$ ，即求：
$$
\sum_{i=1}^n\sum_{j=0}^{i-1}{n\choose i}\times p^i\times (1-p)^{n-i}\times {n\choose j}\times q^j \times (1-q)^{n-j}
$$
化简，得：
$$
\sum_{i=1}^n {n\choose i}\times p^i\times (1-p)^{n-i}\times(\sum_{j=0}^{i-1}{n\choose j}\times q^j \times (1-q)^{n-j})
$$
$O(n)$ 预处理逆元与 $p$、$q$ 的 $n$ 次方即可。组合数可以递推计算以卡常。

注意实现细节，本题还是挺水的。

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 10000005;
const int mod = 1e9 + 7;

inline int qpow(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = 1ll * ret * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return ret;
}
int inv[maxn];

int n, ans;
int p, q, p2, q2;
int invp2, invq2;
int pa, pb, qa, qb;
int powp, powq;
int powp2, powq2;
int sq;
int C;

int main() {
	scanf("%d", &n);
	scanf("%d%d", &pa, &pb);
	p = 1ll * pa * qpow(pb, mod - 2) % mod;
	p2 = (1 - p + mod) % mod;
    scanf("%d%d", &qa, &qb);
	q = 1ll * qa * qpow(qb, mod - 2) % mod;
	q2 = (1 - q + mod) % mod;
	if (p == 1)
		return printf("%d", (1 - qpow(q, n) + mod) % mod), 0;
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    }
    C = 1;
    powp = 1, powq = 1;
    powp2 = qpow(p2, n), powq2 = qpow(q2, n);
    invp2 = qpow(p2, mod - 2), invq2 = qpow(q2, mod - 2);
    int tp = 1ll * powp * powp2 % mod, tq = 1ll * powq * powq2 % mod;
    int mp = 1ll * p * invp2 % mod, mq = 1ll * q * invq2 % mod;
	sq = powq2;
	for (int i = 1; i <= n; ++i) {
		C = 1ll * C * (n - i + 1) % mod * inv[i] % mod;
        tp = 1ll * tp * mp % mod;
        tq = 1ll * tq * mq % mod;
        ans = (ans + 1ll * tp % mod * sq % mod * C) % mod;
		sq = (sq + 1ll * tq % mod * C) % mod;
	}
	printf("%d", ans);
	return 0;
}

# 数学, 概率

题解-LibreOJ-6513「雅礼集训 2018 Day10」足球大战

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!