HDU 4624 Endless Spin

发表于 | 分类于

Description

有\(n\)个球排成一列，初始时都为白色。

每次操作都从所有可能的区间里等概率选择一个，将其中的球都染黑。直到所有球都染黑，这个游戏才结束。

求期望的操作次数。

\(T\)组数据（\(T\leq 50\)），\(1\leq n\leq 50\)。

Solution

感觉算是MIN-MAX容斥期望题的鼻祖了……？

我们要求的东西事实上是一个\(\mathrm{E}[\max\{X_i\}]\)，其中\(X_i\)表示第\(i\)个球被染黑的时间。这个东西并不好做，我们MIN-MAX容斥一下，问题就转化成了求被染黑时间的最小值，也就是这个集合第一次有点被染黑的时间的期望值。

然而我们发现求一个集合第一次有点被染黑时间的期望值也并不好做……注意到对于离散型期望有结论\(\mathrm{E}[X]=\sum_{i = 1}^{+\infty}P(X\geq i)\)，而\(P(X_i\geq x) = p_i^{x - 1}\)（这里\(p_i\)表示选中区间和我们的那个集合不相交的概率），也就是说最后的期望是一个无穷级数： \[ \sum_{k = 0}^{+\infty} p_i^k \] 利用等比数列求和公式可以得到这个东西就事\(\frac{1}{1 - p_i}\)（请注意这里的集合非空，所以\(p_i\in [0,1)\)，所以这个式子成立），那么我们接下来就要考虑怎么高消的处理所有集合的贡献。

注意到如果不考虑系数的话集合的贡献只和和该集合不相交的区间数有关。因此我们定义状态\(f_{i, j, 0/1}\)表示前\(i\)个点，不和我们选择集合相交的区间有\(j\)个，集合奇偶性为\(0/1\)的情况，转移很容易，然后就做完了……

注意那个卡精有毒……所以需要高精小数，然后我现学现卖了一波Java操作（逃

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Scanner;
import java.io.*;
import java.math.BigDecimal;

public class Main {
  public static long C2(long x) {
    return x * (x - 1) / 2;
  }
  public static long S2(long x) {
    return x * (x + 1) / 2;
  }
  
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    long [][][]f = new long[55][1300][2];
    BigDecimal []E = new BigDecimal[55];
    for(int i = 0; i < 55; i ++) {
      for(int j = 0; j < 1300; j ++) {
        f[i][j][0] = f[i][j][1] = 0;
      }
    }
    f[0][0][0] = 1;
    for(int i = 1; i <= 50; i ++) {
      for(int j = 0; j <= S2(i); j ++) {
        for(int k = 0; k < 2; k ++) {
          // f[i][j][k] = 0;
          for(int t = i - 1; t >= 0 && S2(i - t - 1) <= (long)j; t --) {
            f[i][j][k] += f[t][j - (i - t) * (i - t - 1) / 2][k ^ 1];
          }
        }
      }
    }
    for(int n = 1; n <= 50; n ++) {
      E[n] = new BigDecimal(0);
      long S = S2(n);
      for(int i = 0; i <= n; i ++) {
        for(int j = 0; (long)j <= S2(i); j ++) {
          for(int k = 0; k < 2; k ++) {
            if(f[i][j][k] == (long)0) continue;
            if(S - (long)j - S2(n - i) == (long)0) continue;
            BigDecimal delta = new BigDecimal(1);
            BigDecimal a = new BigDecimal((long)j + S2(n - i));
            BigDecimal b = new BigDecimal(S);
            delta = delta.subtract(a.divide(b, 50, BigDecimal.ROUND_HALF_UP));
            if(k == 0) delta = delta.multiply(new BigDecimal(-1));
            BigDecimal temp = new BigDecimal(f[i][j][k]);
            E[n] = E[n].add(temp.divide(delta, 50, BigDecimal.ROUND_HALF_UP));
          }
        }
      }
    }
    int T = in.nextInt();
    for(int i = 1; i <= T; i ++) {
      int n = in.nextInt();
      System.out.printf("%.15f\r\n",E[n]);
    }
  }
}