BZOJ2201 彩色圆环 <概率DP>

Posted on Symbols count in article: 612 Reading time ≈ 2 mins.

Problem

彩色圆环

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  259  MB\mathrm{Memory\;Limit:\;259\;MB}

Description

Input

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

Output

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

Sample Input

1
8 1

Sample Output

1
8.00000

HINT

100%100\%的数据满足1≤N≤2001\le N\le200，1≤M≤1091\le M\le10^9。

标签：概率DP

Solution

考虑用期望DP\mathrm{DP}。用f[i][0/1]f[i][0/1]表示ii颗珠子，首尾颜色相同(1)(1)/不相同(0)(0)的期望美观程度。枚举最后一节相同颜色珠子的长度进行转移。需要先预处理p[i]p[i]表示连续ii颗珠子颜色相同的概率。

  • 边界：f[1][1]=1f[1][1]=1

  • 状态转移：

    f[i][0]=∑j=1i−1(f[i−j][0]⋅p[j]⋅j⋅(1−2m)+f[i−j][1]⋅p[j]⋅j⋅(1−1m))f[i][1]=∑j=1i−1f[i−j][0]⋅p[j]⋅j⋅1mf[i][0]=\sum_{j=1}^{i-1}(f[i-j][0]\cdot p[j]\cdot j\cdot(1-\frac{2}{m})+f[i-j][1]\cdot p[j]\cdot j\cdot(1-\frac{1}{m}))\\ f[i][1]=\sum_{j=1}^{i-1}f[i-j][0]\cdot p[j]\cdot j\cdot\frac{1}{m}

  • 答案：Ans=∑i=1n−1f[n−i+1][0]⋅p[i]⋅i⋅iAns=\sum_{i=1}^{n-1}f[n-i+1][0]\cdot p[i]\cdot i\cdot i

对于状态转移的部分，上式中1−2m1-\frac{2}{m}是新加入的一串颜色不能和原来的首和尾颜色相同，1−1m1-\frac{1}{m}是新加入的一串颜色不能和原来的首和尾相同，而原来的首和尾同色；下式中1m\frac{1}{m}是新加入的一串颜色必须和原来的首相同。
对于统计答案的部分，枚举的ii代表首所在的颜色连续段的长度为ii，这样的串有ii种，每种的这个部分贡献为ii，剩下部分期望贡献为f[n−i+1][0]f[n-i+1][0]。
时间复杂度O(n2)O(n^2)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n; dnt m, ans;
dnt p[205], f[205][2];
int main() {
    read(n), read(m);
    m = 1.0/m, p[1] = 1, f[1][1] = 1;
    for (int i = 2; i <= n; i++) p[i] = p[i-1]*m;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            f[i][0] += f[i-j][0]*p[j]*j*(1-2*m), 
            f[i][0] += f[i-j][1]*p[j]*j*(1-m), 
            f[i][1] += f[i-j][0]*p[j]*j*m;
    for (int i = 1; i < n; i++)
        ans += f[n-i+1][0]*p[i]*i*i;
    ans += p[n]*n;
    return printf("%.5lf\n", ans), 0;
}