#P18714. How Many Rounds Are Expected?
How Many Rounds Are Expected?
How Many Rounds Are Expected?
有 个集合,第 个集合中有 个元素。总共有 个不同的元素,每个元素恰好属于一个集合,且 。
每一轮进行以下随机操作:在所有元素的完美匹配中等概率选择一种,把 个元素配成 对。对于每一对,独立、等概率选择其中一个元素,把它从原集合移出,放入同对另一个元素所属的集合。
一轮中所有移动根据本轮操作前的所属集合同时进行。元素身份保持不同;初始同属一个集合的元素也分别参与匹配。空集合不会影响后续操作。
求所有元素第一次属于同一个集合时,已经进行的轮数的期望。如果初始已经同属一个集合,轮数为零。
输出该期望对 取模的结果。
输入格式
第一行是测试数据组数 ,。
每组第一行有两个整数 ,满足 。
第二行给出 个整数 ,满足 且 。
所有测试组的 之和不超过 , 之和不超过 。
输出格式
每组输出一个整数,表示期望轮数模 的值。若期望写成有理数 ,应输出满足 的剩余类 。
样例 1
4
2 1
1 1
2 2
2 2
2 2
1 3
3 2
1 1 2
1
3
499122179
499122180
对于第一组,唯一的匹配中无论选哪个元素移动,一轮后都只有一个非空集合,所以期望为 。
对于第二组,把状态写成 。有 种完美匹配,每种匹配有 种移动元素的选择,总计 种等概率操作。其中 种得到 ,另外 种仍为 ,期望是 。
对于第三组, 的 种操作中, 种得到 ,另 种得到 。期望为 ,模意义下为 。
对于第四组, 的 种操作中, 种得到 ,另 种得到 。期望为 ,模意义下为 。
样例 2
3
6 5
2 1 1 3 1 2
10 100
90 12 18 1 1 24 7 4 37 6
10 200
102 19 25 11 43 97 19 28 11 45
347465837
225202828
437065763