抽卡【牛客tracker 每日一题】
抽卡
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
王子连接的国服终于上线啦~
已知王子连接的抽卡系统如下：
共有n nn个卡池，第i ii个卡池共有a i a_iai种卡，每张卡的出货率都是相等的（也就是说该卡池单次抽卡，每种卡出货率是1 / a i 1/a_i1/ai）。
第i ii个卡池中，你有b i b_ibi种卡是自己很想要的。
现在的问题是，如果每个卡池里都单抽一次，能抽到自己想要的卡的概率是多少？
可以证明，这个概率一定可以写成a / b a/ba/b形式的分数。最后输出该分数在模10 9 + 7 10^9+7109+7意义下的值就可以了。
即输出满足b ∗ x % 1000000007 = a b∗x\%1000000007=ab∗x%1000000007=a的最小非负整数x xx。
输入描述：
第一行输入一个正整数n （ 1 ≤ n ≤ 100000 ） n（1≤n≤100000）n（1≤n≤100000）。
第二行输入n nn个正整数a i a_iai。
第三行输入n nn个正整数b i b_ibi，代表第i ii个卡池的你想要的卡种类数量。（ 1 ≤ b i ≤ a i ≤ 100000 ） （1≤b_i≤a_i≤100000）（1≤bi≤ai≤100000）
输出描述：
一个整数，表示该概率在模10 9 + 7 10^9+7109+7意义下的值。
示例1
输入：
2 3 4 1 1输出：
500000004说明：
能抽到自己想要的卡的概率是1 / 2 1/21/2，由于2 ∗ 500000004 % 1000000007 = 1 2*500000004\%1000000007=12∗500000004%1000000007=1，故输出500000004 500000004500000004。
解题思路
本题核心是对立事件概率计算+模逆元求解抽卡概率，适配大数取模要求。直接计算抽到想要卡的概率较复杂，转化为对立事件：总概率= 1 − = 1 -=1−所有卡池都抽不到想要卡的概率乘积。每个卡池抽不到的概率为( a i − b i ) / a i (a_i-b_i)/a_i(ai−bi)/ai，因模数10 9 + 7 10^9+7109+7是质数，用快速幂计算a i a_iai的乘法逆元实现分数取模。遍历所有卡池累乘抽不到的概率，最后用1 11减去该结果并对模数取模，得到最终答案。算法时间复杂度O ( n log p ) O(n\log p)O(nlogp)，完美适配n ≤ 10 5 n≤10^5n≤105的大数据规模。
总结
核心逻辑：利用对立事件简化概率计算，通过乘法逆元处理模运算下的分数除法。
关键操作：快速幂求逆元，累乘所有卡池抽不到的概率，计算最终合法概率。
效率保障：线性遍历卡池，快速幂对数级计算逆元，高效满足题目时间与数据限制。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e5+10;constll p=1e9+7;constll INF=1e18;constll M=2e3+10;ll q1[N],q2[N];llqmi(ll a,ll b){ll res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b>>=1;}returnres;}intmain(){ll n;cin>>n;for(ll i=1;i<=n;i++)cin>>q1[i];for(ll i=1;i<=n;i++)cin>>q2[i];ll ans=1;for(ll i=1;i<=n;i++){ll x=(q1[i]-q2[i])*qmi(q1[i],p-2)%p;ans=(ans*x)%p;}cout<<(1-ans+p)%p;return0;}