P5516 [MtOI2019] 小铃的烦恼

在幻想乡中，本居 小铃(Motoori Kosuzu)不仅经常被人撞，还要整理铃奈庵的书籍，她有很多烦恼。

小铃每天都会整理一次铃奈庵的书籍。这次桌子上有 $n$ 本魔法书，这些书一次排成一排，每本书有一个魔法属性和编号。 最开始这些书的魔法属性都是一样的，但是因为被人多次使用，魔法属性发生了变化，小铃想让所有书的魔法属性重新全部相同。 这次小铃找到了雾雨 魔理沙(Kirisame Marisa)帮忙整理书籍，每次魔理沙可以释放选定魔法，魔法会随机选择两本书 $a,b$ ( $a$ 不等于 $b$ )。 选定这两本书后，魔理沙会释放转移魔法，使得有 $p_{a,b}\ (p_{a,b}\in (0,1])$ 的概率，第 $b$ 本书的魔法属性变成第 $a$ 本书的魔法属性。也就是说有 $1-p_{a,b}$ 的概率，使得你**即使选定了 $a,b$ 两本书，但是魔法属性的转移不成功，意味着这次操作是无效的** 。 注意 $p_{a,b}$ 是对于**转移是否成功的概率**，和随机选择两本书的操作互不影响。 现在小铃想知道，求期望操作多少次，才能使所有的书魔法属性都一样？由于时间紧迫，小铃找到了你，希望你可以帮其解决这个问题，不然小铃就不会给你这题的分了。

无

无

对于前 $10\%$ 的数据，$n\leq 10$，且最多有一种不同的魔法属性。 对于另外 $20\%$ 的数据，$n\leq10$，且最多有两种不同的魔法属性，并且其中一种的魔法属性的个数小于等于 $1$ 。 对于 $100\%$ 的数据，$n\leq2\times 10^3$ 。 对于所有数据，满足 $\left(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^{n}p_{a,b}\right) = n^2$ 。 ### 题目来源 [迷途之家2019联赛](https://www.luogu.org/contest/20135)(MtOI2019) T3 出题人：Qiuly