【题意】：略。
【题解】：设dp[i][j]表示左边有i个洞亮，右边有j个洞亮离目标状态的期望。
然后所有dp[ii][jj](ii >= i && jj >= j)都是dp[i][j]的后继状态，由期望计算公式可以算出dp[i][j]的期望。
这里转移会有个环，移项即可处理掉。
要先预处理组合数、p的幂和(1-p)的幂。
最后答案即为dp[0][0].
用记忆化搜索来写非常方便。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 110
22 double dp[55][55];
23 double p1[maxn], p2[maxn];
24 double C[55][55];
25 int n, m;
26 double p;
27 bool visit[55][55];
28 void init() {
29 for(int i = 0; i < 51; i++) C[i][0] = C[i][i] = 1;
30 for(int i = 2; i < 51; i++)
31 for(int j = 1; j < i; j++)
32 C[i][j] = C[i-1][j-1] + C[i-1][j];
33 }
34
35 double dfs(int a, int b) {
36 double &tmp = dp[a][b];
37 if(visit[a][b]) return tmp;
38 visit[a][b] = true;
39 if(a >= m && b >= m) return tmp = 0.0;
40 tmp = 1.0;
41 for(int i = 0; i <= n - a; i++) {
42 for(int j = 0; j <= n - b; j++) {
43 if(i == 0 && j == 0) continue;
44 tmp += (dfs(a + i, b + j)) * p1[i+j] * p2[2 * n - a - b - i - j] * C[n-a][i] * C[n-b][j];
45 }
46 }
47 return tmp /= (1 - p2[2 * n - a - b]);
48 }
49
50 int main() {
51 init();
52 while(~scanf("%d%d%lf", &n, &m, &p)) {
53 if(!n && !m) break;
54 p1[0] = p2[0] = 1.0;
55 for(int i = 1; i < maxn; i++) p1[i] = p1[i-1] * p;
56 for(int i = 1; i < maxn; i++) p2[i] = p2[i-1] * (1 - p);
57 memset(visit, false, sizeof(visit));
58 printf("%.6f\n", dfs(0, 0));
59 }
60 return 0;
61 }
62