【题解】[CTSC2006]歌唱王国
[CTSC2006]歌唱王国
$T$ 组询问，每次给出长度为 $m$ 的序列 $a$。
现在你将生成一个随机序列，字符集为 $1-n$，每次在序列末尾等概率随机一个数。当 $a$ 成为了随机序列中的一个连续子序列则结束随机。
询问随机序列的期望长度。
$1\le T\le 50, 1\le n,m\le 10^5$。
$T$ 组询问，每次给出长度为 $m$ 的序列 $a$。
现在你将生成一个随机序列，字符集为 $1-n$，每次在序列末尾等概率随机一个数。当 $a$ 成为了随机序列中的一个连续子序列则结束随机。
询问随机序列的期望长度。
$1\le T\le 50, 1\le n,m\le 10^5$。