发布者:edward_mj 7月 19, 2011 [SGU385 Highlander][数学期望][组合数学][动态规划]有2条评论
输入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