题意:

一个长度为 n 的区间,刚开始时区间中所有元素都是白色。
每一次均匀随机一个子区间,将这个子区间染成黑色。
期望多少次将整个序列染黑。
n ≤ 50
陈立杰的题, emmmm

分析:

随机变量(\chi):
对于一次实验结果我们可以一个变量的数值, 这个变量的取值随偶然因素变化
但又遵从一定的概率分布规律,这种变量叫做随机变量

有公式:

E(\chi) = \sum_{k=0}^{\infty} k \cdot Pr(\chi = k) = \sum_{x = 0} ^ {\infty} Pr(\chi > k)

其中, 我们令Pr(x) 表示概率.这个式子其实就是利用了一个前缀和的思想而已!

那么在这题之中, Pr(\chi > k) 就变成了k次覆盖, 不会将整个棋盘变成黑色的概率

我们考虑单独一个k, 假设A_i 表示no.i个点最后是白点的概率, 我们其实就是求|A_1 \cup A_2 \cup A_3…\cup A_n|的概率

于是我们就可以容斥了…

就是求|A_{a_1}\cap A_{a_2} …\cap A_{a_n}|考虑一下,不难发现就是要求{a_1, a_2…a_n}这些点都是白点的概率, 这个就很好求了

我们假设 a_0 = 0, a_{n+1} = n + 1

p(a_1, a_2…a_n) = \frac{\frac 1 2 \sum_{i=0} ^ n (a_{i + 1} – a_i – 1) \cdot (a_{i + 1} – a_i)}{\binom n 2 + n}

那么k次覆盖就是上述式子的k次方就好了!

对原式进行化简我们有:

\begin{gathered}
\sum_{k=0}^{\infty} Pr(\chi > k)&=&\sum_{k=0}^{\infty}\sum_{r=1}^n\sum_{1\leq a_1 \leq a_2 …\leq a_r} p^k(a_1,a_2\dots a_r)\\
&=&\sum_{r=1}^n\sum_{k=0}^{\infty}\sum_{1\leq a_1 \leq a_2 …\leq a_r} p^k(a_1,a_2\dots a_r)\\
&=&\sum_{r=1}^n\sum_{1\leq a_1 \leq a_2 …\leq a_r} \frac{1}{1-p(a_1,a_2 \dots a_r)}
\end{gathered}

然后我们就可以在2的次幂的时间内完成这一道题目了, 但是由于n是50左右的范围, 还是需要优化一下, 考虑dp转移: dp[i][j][k] 表示最后一个白点在i号位置,j为选取的白点数的奇偶性, 可选的区间的方案数为k的子集数目, 那么我们就可以枚举最后的可选区间数然后dp转移了, 详见代码!

Code:

Ps: 首先声明一点, 这道题目会了正解可能还有要高精度, 但是本人用了\colorbox{red}{float128} 来搞事情! 但是HDU好像不给力, 最后就草草的打表过了…

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
typedef __float128 f128;

# define R register
# define P pair<int, int>
# define lowbit(x) ((x) & (~x + 1))

const int N = 53;
const f128 eps = 1e-18;

int T, n;
f128 ans, dp[N][2][N * (N + 1) >> 1];


inline int calc(int x, int y)
{
    return (y - x - 1) * (y - x) / 2;
}
int main()
{
    scanf("%d", &T);
    for(int _ = 1; _ <= T; _++)
    {
        ans = 0;
        scanf("%d", &n);
        dp[0][0][0] = 1;
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j < 2; ++j)
                for(int k = ((i + 1) * i >> 1); ~k; --k)
                {
                    dp[i][j][k] = 0;
                    for(int u = 0; u < i; u++) if(k >= calc(u, i))
                        dp[i][j][k] += dp[u][j ^ 1][k - calc(u, i)];
                    if(!dp[i][j][k]) continue;
                    f128 res = (f128)(k + calc(i, n + 1)) / (n * (n + 1) / 2); 
                    // if(res - 1.0 < eps && 1.0 - res < eps) continue;
                    res = dp[i][j][k] / (1 - res);
                    if(j) ans += res;
                    else ans -= res;
                }
        long double Ans = ans;
        printf("%.15Lf\n", Ans);
    }
    return 0;
}

Leave a Reply