2013年多校的题目，那个时候不太懂怎么做，最近重新拾起来，看了一下出题人当初的解题报告，再结合一下各种情况的理解，终于知道整个大致的做法，这里具体写一下做法。
题意：给你一段长度为[1..n]的白色区间，每次随机的取一个子区间将这个区间涂黑，问整个区间被涂黑时需要的期望次数。
1. 首先要做的是一个题目的转化。如果我定义pi为 恰好i次将区间涂黑的概率，那么显然期望 E= 0*p0+1*p1+2*p2+... 换一种角度看这个公式，其实这个公式可以这么写
E = p1 + p2 + p3 + p4 + p5 + ...
p2 + p3 + p4 + p5 + ...
p3 + p4 + p5 + ...
定义Li=p(i+1) + p(i+2) + ... 那么我们可以把Li理解成覆盖了i次都没有将整个区间涂黑的概率。
所以E=L0+L1+L2+...
2. 理解了上面这一点之后我们可以先考虑一种暴力的做法，那就是枚举2^n个最后留下来的点，譬如最后留下来的点是v1,v2,v3...vk，那么实际上可选的区间只有[1,v1-1],[v1+1,v2-1],[v2+1,v3-1]...那么这里区间的选法就有A种（A是可以求出来的），要使这些点都能被留下来，那么我们每次选的只能是这A个区间，因而概率 p = A/ ((n+1)*n/2). 那么对于Li来说 Li += p^i* (-1)^(k－1). 之所以要乘(-1)^k是因为这里需要有一个容斥。考虑到p^i的累加和即 p+p^1+p^2+... = 1/(1-p) 所以对于每个2^n，它对最后期望的影响实际上是 1/(1-p)*(-1)^(k-1).
3. 暴力的想法给到了，那么下面就是要优化一下这种做法了，因为我总不可能2^50枚举所有剩下的点。一个自然的想法是考虑dp，看上面的式子我们不难发现实际上最后起作用的是 A和k的奇偶性，而A的范围是有限的（总的区间个数），那么我们可以定义一个状态dp[i][j][k]表示，第i个点是白点（未被覆盖），且前i个白点的奇偶性为j，可选区间的个数为k有多少个子集。 那么对于一个期望值E[n]来说(n>=i) 这个状态对E[n]的影响实际上是
可选的区间 A = 前i个点的可选区间数+ [i...n]这一段为黑的可选区间数 ＝ k+(n-i+1)(n-i)/2;
p = A/（(n+1)*n/2）;
E[n] += dp[i][j][k]*(1-p)*(-1)^(j-1)；
dp状态的转移具体可以参考一下下面的代码。
4. 题目的第二个坑点就在于它需要有15个小数点的精度，所以需要写一个高精度类，这里只需要涉及两个浮点数的加法和减法就可以了，所以写的时候还是挺容易的，注意答案是round到15个小数点，所以如果小数点后第16个数是>=5的，输出之前还要将结果加上一个1e-15.
下面贴两分代码，一份是不需要高精度的时候的dp的代码，另外一份是要高精度的代码。
#pragma warning(disable:4996)#include#include #include #include #include #include #include #include #include
#include using namespace std;#define ll long long#define maxn 55ll dp[maxn][2][maxn*(maxn + 1) / 2];double E[maxn];int main(){ memset(dp, 0, sizeof(dp)); memset(E, 0, sizeof(E)); dp[0][0][0] = 1; for (int i = 0; i <= 50; ++i){ for (int j = 0; j <= (i + 1)*i / 2; ++j){ if (dp[i][0][j]) { for (int k = i + 1; k <= 50; ++k){ dp[k][1][j + (k - i)*(k - i - 1) / 2] += dp[i][0][j]; } } if (dp[i][1][j]){ for (int k = i + 1; k <= 50; ++k){ dp[k][0][j + (k - i)*(k - i-1) / 2] += dp[i][1][j]; } } } } for (int i = 1; i <= 50; ++i){ for (int k = 0; k <= i; ++k){ for (int j = 0; j <= (k + 1)*k / 2; ++j){ if (dp[k][0][j]){ long double p = (j + (i - k + 1)*(i - k) / 2 + .0) / ((i + 1)*i / 2); if (p == 1.0) { continue; } E[i] -= dp[k][0][j] / (1 - p); } if (dp[k][1][j]){ long double p = (j + (i - k + 1)*(i - k) / 2 + .0) / ((i + 1)*i / 2); if (p == 1.0) { continue; } E[i] += dp[k][1][j] / (1 - p); } } } } int xx; cin >> xx;}
#pragma warning(disable:4996)#include#include #include #include #include #include #include #include #include
#include using namespace std;#define ll long long#define maxn 55#define maxdp 50struct BigDecimal{ ll ip; int dp[maxdp]; BigDecimal(){ ip = 0; memset(dp, 0, sizeof(dp)); } BigDecimal(int x){ ip = x; memset(dp, 0, sizeof(dp)); } BigDecimal(ll x, ll y) { ip = x / y; x = abs(x); y = abs(y); x = x%y; for (int i = 0; i < maxdp; ++i){ x *= 10; dp[i] = x / y; x %= y; } }};BigDecimal operator + (const BigDecimal &a, const BigDecimal &b){ BigDecimal ret; int carry = 0; for (int i = maxdp - 1; i >= 0; --i){ ret.dp[i] = (a.dp[i] + b.dp[i] + carry) % 10; carry = (a.dp[i] + b.dp[i] + carry) / 10; } ret.ip = a.ip + b.ip + carry; return ret;}BigDecimal operator - (const BigDecimal &a, const BigDecimal &b){ BigDecimal ret; int marry = 0; for (int i = maxdp - 1; i >= 0; --i){ ret.dp[i] = (a.dp[i] - b.dp[i] - marry + 10) % 10; marry = a.dp[i] - b.dp[i] - marry < 0 ? 1 : 0; } ret.ip = a.ip - b.ip - marry; return ret;}void print(const BigDecimal& x, int digits){ printf("%I64d.", x.ip); BigDecimal y; if (x.dp[digits] >= 5){ y.dp[digits - 1] = 1; } y = x + y; for (int i = 0; i < digits; ++i){ printf("%d", y.dp[i]); } puts("");}ll dp[maxn][2][maxn*(maxn + 1) / 2];BigDecimal Ep[maxn];BigDecimal En[maxn];BigDecimal E[maxn];int main(){ memset(dp, 0, sizeof(dp)); memset(E, 0, sizeof(E)); dp[0][0][0] = 1; for (int i = 0; i <= 50; ++i){ for (int j = 0; j <= (i + 1)*i / 2; ++j){ if (dp[i][0][j]) { for (int k = i + 1; k <= 50; ++k){ dp[k][1][j + (k - i)*(k - i - 1) / 2] += dp[i][0][j]; } } if (dp[i][1][j]){ for (int k = i + 1; k <= 50; ++k){ dp[k][0][j + (k - i)*(k - i - 1) / 2] += dp[i][1][j]; } } } } for (int i = 1; i <= 50; ++i){ ll all = ((i + 1)*i / 2); for (int k = 0; k <= i; ++k){ for (int j = 0; j <= (k + 1)*k / 2; ++j){ if (dp[k][0][j]){ ll select = j + (i - k + 1)*(i - k) / 2; if (select == all) continue; En[i] = En[i] + BigDecimal(all*dp[k][0][j], all - select); } if (dp[k][1][j]){ ll select = j + (i - k + 1)*(i - k) / 2; if (select == all) continue; Ep[i] = Ep[i] + BigDecimal(all*dp[k][1][j], all - select); } } } E[i] = Ep[i] - En[i]; } int T; cin >> T; int n; while (T--) { cin >> n; print(E[n], 15); } return 0;}