清橙A1202&Bzoj2201：彩色圆环

因为Bzoj是权限题，所以可以去清橙做一下

---

Sol

突然考了一道这样的题，考场上强行\(yy\)出来了

win下评测Long double爆零TAT

首先肯定是破环为链变成序列问题辣

那么就要求第一个的颜色和最后的颜色不同

怎么统计，枚举前面有多长和右面有多长长度相等

中间的强制第一个与枚举的前面不同，以及最后一个与枚举的后面(就是前面)不同

合起来就是答案

考虑中间的怎么算

设\(f[0/1][i]\)表示到第\(i\)个位置，颜色与枚举的前面相同(\(1\))，不同(\(0\))的期望得分

转移：枚举小于\(i\)的\(j\)转移过来

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

IL int Input(){

    RG int x = 0, z = 1; RG char c = getchar();

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int n;

long double ans, f[2][205], dv[205], m;

int main(RG int argc, RG char* argv[]){

	n = Input(), m = Input(), dv[0] = 1;

	for(RG int i = 1; i <= n; ++i) dv[i] = dv[i - 1] / m;

	f[1][0] = 1;

	for(RG int i = 1; i <= n; ++i)

		for(RG int j = 0; j < i; ++j){

			f[1][i] += f[0][j] * (i - j) * dv[i - j];

			f[0][i] += f[0][j] * (i - j) * (m - 2) * dv[i - j];

			f[0][i] += f[1][j] * (i - j) * (m - 1) * dv[i - j];

		}

	ans = 1.0 * n * m * dv[n];

	for(RG int i = 1; i < n; ++i)

		for(RG int j = 0; j + i < n; ++j)

			ans += 1.0 * (j + i) * m * dv[j + i] * f[0][n - j - i];

	printf("%.10Lf\n", ans);

    return 0;

}