在一个D维空间，只有整点，点的每个维度的值是0~n-1 。现每秒生成D条线段，第i条线段与第i维度的轴平行。问D条线段的相交期望。
生成线段[a1,a2]的方法（假设该线段为第i条，即与第i维度的轴平行）为，i!=j时，a1[j]=a2[j]，且随机取区间[0,n-1]内的整数。然后a1[i],a2[i]在保证a1[i]<a2[i]的前提下同样随机。
由于D条线段各自跟自己维度的轴平行，我们可以转换成只求第i个维度与第j个维度的相交期望，然后乘以C(2,n)就好了
显然线段[a1,a2]和线段[b1,b2]要有交点，则k!=i&&k!=j时(a1[k]==a2[k],b1[k]==b2[k]这2个是必然有的)必须要有，a1[k]==b1[k]. 这个的概率是1/n
所以k!=i&&k!=j时，概率期望是(1/n).pow(D-2)
下面看k==i的情况，k==j的情况是一样的。k==i的时候a1[k]<a2[k],b1[k]==b2[k].则我们求的是a1[k]<=b1[k]<=a2[k]&&a1[k]<a2[k]的概率。
即，3个随机数a,b,c. 求P(a<=b<=c && a<c).可用一个x轴画图示意。取任意一点b=i(0<=i<=n-1)。满足的有a<i&&c>i和a==i&&c>i和a<i&&c==i。
3种情况数分别是(i-0)*(n-1-i), n-1-i, i-0.
随机取b点位置的方案数是n，选取线段[a,c]的方案数是C(2,n)，所以要将所有的相交次数除以这2个方案数，就是相交的期望
所以P(a<=b<=c && a<c) = ∑((1/n)*(1/C(2,n))*(i*(n-1-i)+n-1-i+i)) = 1/(n*C(2,n))*∑(-i*i+(n-1)*i+n-1), 其中0<=i<=n-1
这个化简得到P(a<=b<=c && a<c) = (n+4)/(3*n)
所以线段[a1,a2]和[b1,b2]的相交期望是 P = ( (1/n)^(d-2) ) * ( ( (n+4)/(3*n) )^2 ) = ( (n+4)^2 ) / ( 9*(n^d) )
java大数AC之？还差一步。。。刚刚那个是2个维度的。
所以最后答案应该是C(2,D)*P = ( D*(D-1)/2 * (N+4)^2 ) / ( 9*(N^D) )
第一次打这样的推公式=。=其实推公式主要是定下来动手慢慢耐心推。。。。
打得我都晕了，好多括号，不知道有没错。。。。
1 import java.math.BigInteger; 2 import java.util.Scanner; 3 4 public class Main { 5 public static void main(String[] agrs){ 6 Scanner scan = new Scanner(System.in); 7 int n,d; 8 while(scan.hasNext()){ 9 n=scan.nextInt(); 10 d=scan.nextInt(); 11 if(d==1){ 12 System.out.println("0"); 13 continue; 14 } 15 BigInteger a = new BigInteger("0"); 16 BigInteger b = new BigInteger("0"); 17 a = BigInteger.valueOf(d*(d-1)/2).multiply(BigInteger.valueOf(n+4).pow(2)); 18 b = BigInteger.valueOf(9).multiply(BigInteger.valueOf(n).pow(d)); 19 if(a.equals(b)){ 20 System.out.println("1"); 21 continue; 22 } 23 BigInteger gg = a.gcd(b); 24 a = a.divide(gg); 25 b = b.divide(gg); 26 System.out.print(a); 27 System.out.print("/"); 28 System.out.println(b); 29 } 30 scan.close(); 31 } 32 }