題意：有兩個盒子各有n個糖（n<=2*105），每天随機選1個（機率分别為p，1-p），然後吃掉一顆糖。直到有一天打開盒子一看，這個盒子沒有糖了。輸入n，p，求此時另一個盒子裡糖的個數的數學期望。
思路：假設沒糖的是A盒子，而B盒子還有0~n個糖。由于B盒子還有0個糖的情況的期望必為0，是以省略，隻需要計算1~n的。
（1）當A盒沒有糖時，B盒就可能有1~n個糖，機率為C(n+i，i)*(pn+1)*(1-p)n-i。為啥還帶個大C？這是情況的種數（想象取糖時還有個順序，有C種可能的順序），不然的話，單靠這兩個小于1的數是超級小的。
（2）根據（1）種的機率公式，窮舉B盒可能還有 i 個糖，那麼對于每種情況，期望值為i*C(n+i，i)*(pn+1)*(1-p)n-i，累加這些期望值就行了。同理，B盒沒有糖也是這樣算，隻是機率換成了（1-p）。兩種情況的累加期望就是答案。
（3）這樣還是不行，求C時會爆LL，對p求幂時結果又太小，精度損失嚴重。C(n+i，i)*(pn+1)*(1-p)n-i這個式子的結果本身是不大的。考慮取這個式子對數，化成相加的形式x=logC(n+i，i)+ log(pn+1)+log(1-p)n-i ，（注意指數可以提到前面作為乘的形式），求出x作為指數來求ex這樣就OK了（這個函數是exp(x) ）。
（4）這個C還是很難求，比如當n=200000時，i 還沒有到10時，C(200000+10, 10)就爆了。對此，由于在窮舉i時，C(n+i,i)是可以遞推的，那麼我們可以先将C給逐漸取對數，再相加就行了。遞推是這樣的，c+=log((n+i)/i)。
（5）總複雜度是O(n)。時間在500ms以下。
1 #include <bits/stdc++.h>
2 #define pii pair<int,int>
3 #define INF 0x3f3f3f3f
4 #define LL long long
5 using namespace std;
6 const int N=40086;
7 double cal(double p,int n)
8 {
9 double c=0, ans=0;
10 ans=n*exp((n+1)*log(p)); //第2個盒子取0個的情況：即還剩下n個。
11 for(int i=1; i<n; i++) //在第2個盒子中取了i個。
12 {
13 c+=log((double)(n+i)/i); //log(c)這樣求才能防溢出。
14 ans+=(n-i)*exp( c+ (n+1)*log(p)+ i*log(1-p) );
15 }
16 return ans;
17 }
18
19 int main()
20 {
21 //freopen("input.txt", "r", stdin);
22 int Case=0, n;
23 double p;
24 while(~scanf("%d %lf", &n, &p))
25 printf("Case %d: %.6f\n", ++Case, cal(p, n)+cal(1-p,n) );
26 return 0;
27 } AC代碼
轉載于:https://www.cnblogs.com/xcw0754/p/4753221.html