题解 | #抽卡#

1. 问题建模

本问题的核心在于计算多个独立事件的并集概率。

由于直接计算“至少抽到一个想要的卡”的概率涉及包含排除原理（Inclusion-Exclusion Principle），随着 的增大，组合数项会呈指数级增长。因此，根据概率论的基本性质，计算其补集（余事件）是更优的策略。

概率模型

1. 定义独立事件：设 为在第 个卡池抽到想要卡的事件，。
2. 定义补集事件：设 为在第 个卡池没有抽到想要卡的事件。由于每张卡出货率相等，则：
3. 多池独立性：由于每个卡池的抽取是相互独立的，所有卡池均未抽到想要卡的概率 为各项补集概率的积：
4. 目标概率：至少抽到一个卡池的概率 。

2. 模意义下的有理数运算

题目要求输出在模 意义下的结果。在有限域（Finite Field）上进行概率计算，需要将除法转化为乘法逆元（Multiplicative Inverse）运算。

核心算法：

1. 聚合分式： 为了减少求逆元的次数（求逆元的时间复杂度为 ），我们不逐个计算 。而是将所有分式合并：

2. 模逆元选择： 由于模数 是质数，且根据约束 ，分母 必不为 的倍数。因此，可以使用费马小定理（Fermat's Little Theorem）求逆元：

3. 计算步骤：

   • 计算分子的模积：。
   • 计算分母的模积：。
   • 利用快速幂（Binary Exponentiation）计算 。
   • 计算失败概率 。
   • 最终结果 。

3. 复杂度分析

时间复杂度：

• 线性部分：遍历 个卡池计算分子和分母的乘积，复杂度为 。
• 对数部分：执行一次费马小定理所需的快速幂运算，复杂度为 ，其中 。

空间复杂度： 或

• 若流式读入数据，仅需常数级变量存储中间乘积，空间复杂度为 。
• 若先存储所有 ，空间复杂度为 。

4. 代码实现

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

static constexpr int MOD = 1e9 + 7;

ll power(ll base, ll exp) {
    base %= MOD;
    ll sum = 1;
    while (exp > 0) {
        if (exp % 2) {
            sum = sum * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }
    return sum;
}

ll modInv(ll x) {
    return power(x, MOD - 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n), b(n);

    ll P = 1;
    ll Q = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        Q = (Q * a[i]) % MOD;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        P = (P * (a[i] - b[i])) % MOD;
    }
    ll P1 = ((Q - P) % MOD + MOD) % MOD;
    ll ans = P1 * modInv(Q) % MOD;

    cout << ans << endl;
}