抽卡【牛客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^971097意义下的值就可以了。即输出满足b ∗ x % 1000000007 a b∗x\%1000000007ab∗x%1000000007a的最小非负整数x xx。输入描述第一行输入一个正整数n 1 ≤ n ≤ 100000 n1≤n≤100000n1≤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≤1000001≤bi​≤ai​≤100000输出描述一个整数表示该概率在模10 9 7 10^971097意义下的值。示例1输入2 3 4 1 1输出500000004说明能抽到自己想要的卡的概率是1 / 2 1/21/2由于2 ∗ 500000004 % 1000000007 1 2*500000004\%100000000712∗500000004%10000000071故输出500000004 500000004500000004。解题思路本题核心是对立事件概率计算模逆元求解抽卡概率适配大数取模要求。直接计算抽到想要卡的概率较复杂转化为对立事件总概率 1 − 1 -1−所有卡池都抽不到想要卡的概率乘积。每个卡池抽不到的概率为( a i − b i ) / a i (a_i-b_i)/a_i(ai​−bi​)/ai​因模数10 9 7 10^971097是质数用快速幂计算a i a_iai​的乘法逆元实现分数取模。遍历所有卡池累乘抽不到的概率最后用1 11减去该结果并对模数取模得到最终答案。算法时间复杂度O ( n log ⁡ p ) O(n\log p)O(nlogp)完美适配n ≤ 10 5 n≤10^5n≤105的大数据规模。总结核心逻辑利用对立事件简化概率计算通过乘法逆元处理模运算下的分数除法。关键操作快速幂求逆元累乘所有卡池抽不到的概率计算最终合法概率。效率保障线性遍历卡池快速幂对数级计算逆元高效满足题目时间与数据限制。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e97;constll INF1e18;constll M2e310;ll q1[N],q2[N];llqmi(ll a,ll b){ll res1;while(b0){if(b1)res(res*a)%p;a(a*a)%p;b1;}returnres;}intmain(){ll n;cinn;for(ll i1;in;i)cinq1[i];for(ll i1;in;i)cinq2[i];ll ans1;for(ll i1;in;i){ll x(q1[i]-q2[i])*qmi(q1[i],p-2)%p;ans(ans*x)%p;}cout(1-ansp)%p;return0;}