最近电脑老死机,而且都是我东西快写完没有保存的时候。。。w(゜Д゜)w
题目大意:有 n 个球,每次把一个区间染成黑色,求期望多少次把所有球染黑
设 p(i) 为 i 次操作后还有白球的概率,则答案为
∑i=0∞p[i]
现在要求 p[i]
先假设剩下的球有 k 个,子区间数为 A,共有 n(n+1) 个子区间,可得 p=An(n+1)
因为有 ∑∞i=0pi=11−p ,再配上容斥的系数,贡献为 (−1)k−111−p
考虑到只跟区间个数和白球奇偶性有关,就可以DP做啦~
这道题还有一点就是要保留15位小数,所以窝写了发python(其中有个错,就是定义超过一维数组的时候不能写
a[[0]*M]*N
,而是应写成a[[0 for x in range(M)]for y in range(N)])
结果没有python…(真是一个悲伤的故事…
转java QAQ(换行要写成 \r\n,只写 \n 会PE…
import java.util.Scanner;
import java.io.*;
import java.math.BigDecimal;
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
long [][][]f = new long[][][];
BigDecimal []E = new BigDecimal[];
for (int i = ;i < ;i ++)
for (int j = ;j < ;j ++)
for (int k = ;k < ;k ++) f[i][j][k] = new Long();
for (int i = ;i < ;i ++) E[i] = new BigDecimal("0");
f[][][] = (long);
for (int i = ;i <= ;i ++)
for (int j = ;j <= i * (i + ) / ;j ++)
for (int k = i + ;k <= ;k ++)
{
f[k][][j + (k - i) * (k - i - ) / ] += f[i][][j];
f[k][][j + (k - i) * (k - i - ) / ] += f[i][][j];
}
for (int i = ;i <= ;i ++)
for (int j = ;j <= i;j ++)
for (int k = ;k <= j * (j + ) / ;k ++)
{
if ((k + (i - j) * (i - j + ) / ) / (i * (i + ) / ) == ) continue;
BigDecimal p = new BigDecimal("1.0"),a = new BigDecimal(k + (i - j + ) * (i - j) / ),b = new BigDecimal (i * (i + ) / );
p = p.subtract(a.divide(b,,BigDecimal.ROUND_HALF_UP));
BigDecimal temp = new BigDecimal(f[j][][k] - f[j][][k]);
E[i] = E[i].add(temp.divide(p,,BigDecimal.ROUND_HALF_UP));
}
int T = in.nextInt(),x;
for (int i = ;i <= T;i ++)
{
x = in.nextInt();
System.out.printf("%.15f\r\n",E[x]);
}
}
}