计数问题

形式化题意

给定 A+BA+B 个本质相同的随机变量,在 {1,2,,6}\{1,2,\cdots,6\} 内等概率取值。若两个随机变量 aA,bB,a=ba \in A, b \in B, a=b,则二者相消为 00。求在所有可能的消除完成后,存在 at,aA,t{1,2,,6}a \leq t, a \in A, t \in \{1,2,\cdots,6\} 的概率。对 109+710^9+7 取模。

朴素DP

cic_i 表示随机结果中数值为 iiAA 内变量数;did_i 同理。原题意可以转化为求出 1P(不存在小于等于ta)1-P(\text{不存在小于等于}t\text{的}a)。由概率的定义,我们可以用能造成后者局面的方案总数除以 6A+B6^{A+B} 既是结果。换句话说,原命题的否命题应当满足 i{1,2,,t},cidi\forall i \in \{1,2,\cdots,t\}, c_i \leq d_i

又因为这些随机变量本质相同,则由“可重集的排列数”得,若有确定的 c1,c2,,c6,i=16ci=Ac_{1},c_2,\cdots,c_6, \sum_{i=1}^{6}c_i=A,则掷出对应结果的方案数为 (Ac1)(Ac1c2)(Ai=15cic6)=A!i=16ci!\dbinom{A}{c_1}\dbinom{A-c_1}{c_2}\cdots\dbinom{A-\sum_{i=1}^{5}c_i}{c_6}=\dfrac{\color{blue}A!}{\prod_{i=1}^{6}c_i!} (更多…)

More
  • 2022年9月22日