牛客41614I - It Takes Two of Two

题意

  • 有一个随机数生成器，每次独立、均匀、随机地生成两个在 [1,n][1,n] 的随机数 u,vu,v
  • 有一张图初始时图为空。
  • 流程如下：
    • （1）运行一次随机数生成器，得到 u,vu,v
    • （2）将双向边 u↔vu\leftrightarrow v 添加到图中后，图满足如下条件，则将双向边 u↔vu\leftrightarrow v 添加到图中。
      • 图没有重边，没有自环
      • 每个点的度数 ∈[1,2]\in [1,2]
    • 若不满足上述条件，则回到步骤（1）
    • 将双向边 u↔vu\leftrightarrow v 添加到图中后，无论生成多少次随机数都找不出符合条件的 u,vu,v，则立即停止。
  • 给出 n∈[1,200]n\in[1,200]，问：运行随机数生成器次数的期望。

思路

  • 图内连通块的形态可以分为这两种：环、链
  • 如果将节点数量 >2>2 的长链首尾连接，将变链为环。
  • 但如果将节点数量 =2=2 的短链首尾连接，将产生重边。
  • 因此我们只关心某一种状态下：
    • 未选择过的点的数量、
    • 图中短链的数量、
    • 图中长链的数量
  • 每随机生成一个 u,vu,v，它有可能是：
序号 情况 说明
1 u,vu,v 之前均从未出现过 u↔vu\leftrightarrow v 是一个新的短链
2 uu 之前属于某条短链，而 vv 之前从未出现过 这条短链变成长链
3 uu 之前属于某条长链，而 vv 之前从未出现过 延长这条长链
4 uu 之前属于某条长链，而 vv 属于某条短链 延长这条长链，短链消失
5 uu 之前属于某条短链，vv 之前属于另一条短链 这两条短链合成一条长链
6 uu 之前属于某条长链，vv 之前属于另一条长链 这两条长链合成一条长链
7 uu 和 vv 之前属于同一条长链 这条长链变成一个环
8 以上条件均不符合 需要重新生成 u,vu,v
  • 令 dp[unselect][chain][dual]dp[unselect][chain][dual] 代表当前状态未选择过的点的数量、图中短链的数量、图中长链的数量下，从这个状态出发直到停止的期望运行次数，进行记搜即可。

概率的计算

情况1 p1=Cn2/n2p_1 = C_n^{2} / n^2 情况2 p2=2×(dual×2)×unselect/n2p_2 = 2\times (dual\times 2)\times unselect / n^2 注意分子需要乘以2，因为选择不分先后顺序。 其它的略

期望的计算

  • 令 ∑p=∑情况1～7p\sum p = \sum_{情况1～7}p
  • 则 1−∑p=1-\sum p = 以上条件均不符合的概率，此时需要需要重新生成 u,vu,v。
  • 那么，在当前状态下，不一定仅生成一次随机数就一定能进入到下一个 dp 状态，大约需要生成 1∑p\frac{1}{\sum p} 次（期望值），才进入下一个 dp 状态。
  • 好了，假设现在我生成了若干次随机数，现在已经能够进入下一个 dp 状态了。
  • 那么，dp[unselect][chain][dual]=1∑p+∑情况1～7[dp(next)×p]dp[unselect][chain][dual] = \frac{1}{\sum p}+\sum_{情况1～7}[dp(next)\times p]，这个答案对吗？
  • 错误
  • 原因：
    • 在这个状态中，是先生成若干次随机数，但是对应的一直是情况8，这几次对 dp[unselect][chain][dual]dp[unselect][chain][dual] 的贡献是 1∑p\frac{1}{\sum p}。
    • 直到某一次不再是情况8，此时进入到下一个 dp 状态。但是我们之前算出的概率 pp 是假设 情况8可能发生 的概率，而我们需要的是 情况8一定不发生 的概率。
    • 因此，概率要再除上 ∑p\sum p
  • dp[unselect][chain][dual]=1∑p+∑情况1～7[dp(next)×p∑p]dp[unselect][chain][dual] = \frac{1}{\sum p} + \sum_{情况1～7}[dp(next)\times \frac{p}{\sum p}]

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=54650365