【bzoj2201】彩色圆环

2014年7月25日1,3190

Description

Input

仅有一行,该行给出依次两个正整数N, M,分别表示宝石的个数和宝石在变化时可能变成的颜色种类数。

Output

应仅有一行,该行给出一个实数E(R),表示圆环的“美观程度”的期望值。

Sample Input

8 1

Sample Output

8.00000
【数据规模和约定】
100%的数据满足1 ≤ N ≤ 200, 1 ≤ M ≤ 10^9。

题解

dp[i][j]表示前i个珠子,最后一个珠子和第一个是否相同(0,1)的期望值

这样可以 比较容易地 得到一个n^2的转移

p[i]表示i个珠子的颜色都相同的概率

至于统计答案

ans=p[n]*n表示环上只有一种颜色

for(int i=1;i<n;i++)ans+=i*i*f[n-i][0]*p[i]

这步是枚举第一珠子所在连续段长度,相当于n个位置里,有i个位置是第一珠子所在连续段,故长度i共有i种摆法