HDU 4624 【期望】

最近電腦老當機，而且都是我東西快寫完沒有儲存的時候。。。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]);
        }
    }
}