在一個(gè)D維空間，只有整點(diǎn)，點(diǎn)的每個(gè)維度的值是0~n-1 。現(xiàn)每秒生成D條線段，第i條線段與第i維度的軸平行。問(wèn)D條線段的相交期望。

生成線段[a1,a2]的方法（假設(shè)該線段為第i條，即與第i維度的軸平行）為，i!=j時(shí)，a1[j]=a2[j]，且隨機(jī)取區(qū)間[0,n-1]內(nèi)的整數(shù)。然后a1[i],a2[i]在保證a1[i]<a2[i]的前提下同樣隨機(jī)。

?

由于D條線段各自跟自己維度的軸平行，我們可以轉(zhuǎn)換成只求第i個(gè)維度與第j個(gè)維度的相交期望，然后乘以C(2,n)就好了

顯然線段[a1,a2]和線段[b1,b2]要有交點(diǎn)，則k!=i&&k!=j時(shí)(a1[k]==a2[k],b1[k]==b2[k]這2個(gè)是必然有的)必須要有，a1[k]==b1[k]. 這個(gè)的概率是1/n

所以k!=i&&k!=j時(shí)，概率期望是(1/n).pow(D-2)

下面看k==i的情況，k==j的情況是一樣的。k==i的時(shí)候a1[k]<a2[k],b1[k]==b2[k].則我們求的是a1[k]<=b1[k]<=a2[k]&&a1[k]<a2[k]的概率。

即，3個(gè)隨機(jī)數(shù)a,b,c. 求P(a<=b<=c && a<c).可用一個(gè)x軸畫(huà)圖示意。取任意一點(diǎn)b=i(0<=i<=n-1)。滿足的有a<i&&c>i和a==i&&c>i和a<i&&c==i。

3種情況數(shù)分別是(i-0)*(n-1-i), n-1-i, i-0.

隨機(jī)取b點(diǎn)位置的方案數(shù)是n，選取線段[a,c]的方案數(shù)是C(2,n)，所以要將所有的相交次數(shù)除以這2個(gè)方案數(shù)，就是相交的期望

?

所以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

這個(gè)化簡(jiǎn)得到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大數(shù)AC之？還差一步。。。剛剛那個(gè)是2個(gè)維度的。

所以最后答案應(yīng)該是C(2,D)*P =??( D*(D-1)/2 * (N+4)^2 ) / ( 9*(N^D) )

?

第一次打這樣的推公式=。=其實(shí)推公式主要是定下來(lái)動(dòng)手慢慢耐心推。。。。

?

打得我都暈了，好多括號(hào)，不知道有沒(méi)錯(cuò)。。。。

?

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 } View Code

轉(zhuǎn)載于:https://www.cnblogs.com/nextbin/p/3868123.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的HDU 4873 ZCC Loves Intersection（JAVA、大数、推公式）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。