[51nod 1667]概率好题

日常传送门

Description

他们各有 k1,k2 个集合 [L1i,R1i],[L2i,R2i]

各随机从每个集合中 都取出一个数 组成两个队列 P,Q

设S1=∑Pi,S2=∑Qi

若 S1>S2 甲胜

若 S1=S2 平局

若 S1<S2​ 乙胜

分别求出甲胜、平局、乙胜的概率

概率均为有理数，记为 pq ，则输出答案为 p∗1q(mod(1e9+7))

Solution

确实是一道好题=w=

题面已经透露出容斥的气味♂

尝试转化模型 重新表示 S1=∑(R1i−xi),S2=∑(L2i+yi)

对于 S1,S2 的大小关系 令它们相减 考虑甲胜 （其余均类似）

S1−S2=∑R1i−∑xi−∑L2i−∑yi>0

∴∑R1i−∑L2i>∑xi+∑yi

这个式子亦可以表示作

∑xi+∑yi+k=S=∑R1i−∑L2i(k≥1)

根据套路 左边是三个变量 右边是常量 常见的隔板法即可解决

代码太丑又慢不敢放求放过

Reference

老曹写得比我好多了！

最重要人家是东方记者跑得快！