# [期望DP][纪中]【2010集训队出题】彩色圆环

2021-07-15 22:46:13

# 彩色圆环

（排名不分先后）

## 正文

### T1

GMOJ $$link$$

$f[i][0] += f[j][0] * p[i - j] * (i - j) * (m - 2) / m;$

$f[i][0] += f[j][1] * p[i - j] * (i - j) * (m - 1) / m;$

$f[i][1] += f[j][0] * p[i - j] * (i - j) / m;$

$ans += \left\{\begin{matrix} n~~*~~p[n]\\ \prod_{n-1}^{i = 1}~~f_{i,0}~~* ~~p_{n~~-~~i}~~*~~(n-i)~~*~~(n-i) \end{matrix}\right.$

### Code

#include <bits/stdc++.h>
#define N 205
using namespace std;

int n, m;
double ans;
double f[N][2], p[N];

int main ()
{
scanf ("%d%d", &n, &m);
p[1] = 1.0;
f[0][1] = 1;
for (int i = 2; i <= n; ++ i)
p[i] = p[i - 1] * (1.0 / m);
for (int i = 1; i <= n; ++ i)
{
for (int j = 0; j < i; ++ j)
{
f[i][0] += f[j][0] * p[i - j] * (i - j) * (m - 2) / m;
f[i][0] += f[j][1] * p[i - j] * (i - j) * (m - 1) / m;
/*不同情况分割线*/
f[i][1] += f[j][0] * p[i - j] * (i - j) / m;
}
}
ans = n * p[n];
for (int i = 1; i < n; ++ i)
{
ans += f[i][0] * p[n - i] * (n - i) * (n - i);
}
printf ("%.7lf", ans);
return 0;
}


https://www.cnblogs.com/unknown-future/p/15017884.html