[SGU385 Highlander]【数学期望】【组合数学】【动态规划】

【题意】

输入n,求在所有错位排列中,在最长循环节上点的数目(如果有多个最长循环节,那么这些上面的点都要算)的期望值。

每个错排都是等概率的。

【算法】

论文上的题…写出来加深印象+方便回看。

因为是排列,而且是错排,所以可以看成无自环的多个独立环拼成的图。

F[i][j][k]表示选了i个数里面最长循环节是j,有k个最长循环节时的方案数。

令G[i][j]=Sum(F[i][0..j][k])

初始化F[0][0][0]=1。

F[i][j][k]=

{

G[i-j][j-1]*P(n-i+j,j)/j      k=1           就是在剩下的n-i+j个数里取j个,得到一个长度为j的排列,但是由于是环,可以循环一圈当同样的,所以/j

F[i-j][j][k-1]*P(n-i+j,j)/j/k   k>1      前面和上面一样.后面的/k是把这k个等长的环的顺序上的重复干掉。

}

最后答案就是Sum( F[n][j][k]*j*k ) / d 

d是错排数目。

【CODE】

https://ideone.com/lIAQX

加入对话

2条评论

留下评论

您的电子邮箱地址不会被公开。