題目大意就是N個商店，M個人，每個人進(jìn)入商店這個商店就賺n * d的錢，但是多個人只算一次錢。如果每個人進(jìn)入每個商店的概率相同問最后所有商店期望的賺錢數(shù)是多少。
　　做得超級艱苦，最開始是列錯了式子，推了一個上午，居然還推出了答案，發(fā)現(xiàn)是一個算組合數(shù)的式子，因此超時了。
　　下午請教了吉大牛，發(fā)現(xiàn)我算概率的時候考慮的不對，實際要用到容斥原理。于是又推了一個下午。。。最后式子終于對了但是求不出來和。
　　式子的列法是這樣的：以M個人恰好進(jìn)入了i個不同的商店作為概率分布，那么事件P(i)的概率為(i / N) ^ M - C(i, 1) * ((i - 1) / N) ^ M + C(i, 2) * ((i - 2) / N) ^ M - ...
　　也就是一個容斥原理。然后總的期望E = sigma{C(n, i) * P(i) * i * n * d}，i = 0 ... N。
　　這個式子列出來后怎么也求不出結(jié)果。晚上imems告訴了我一個很簡單的推導(dǎo)方法。對于一個商店來說，一個人不去的概率是(N - 1) / N，那么M個人都不去的概率是((N - 1) / N) ^ M，用1減去這個結(jié)果就是肯定至少有人去這個商店的概率。然后總的期望就乘以N個商店，再乘以賺錢數(shù)n * d就可以了。很巧妙，因為他是從商店的角度直接考慮的問題，而不考慮商店的人數(shù)，這樣就不用列概率分布了。
　　但是上面的公式就不能推導(dǎo)出正確結(jié)果了么，后來又推了一下，發(fā)現(xiàn)是可以的（照著結(jié)果猜- -!）。
　　具體的推導(dǎo)很麻煩，但是總的來說用到了組合數(shù)學(xué)的幾個公式。首先 k * C(n, k) = n * C(n - 1, k - 1)，利用這個公式把外面的i消去。然后有pascal遞推式：C(n, k) = C(n - 1, k) + C(n - 1, k - 1)。我們分別考慮(i / N) ^ M前面的系數(shù)，可以發(fā)現(xiàn)都是兩個二項式系數(shù)相乘的方式。把其中的一個利用pascal公式展開后，出現(xiàn)了形如C(n, 0) - C(n, 1) + C(n, 2) - ...之類的式子，結(jié)果是0，消去了。剩下的還是兩個二項式系數(shù)的乘積，不過都是這種形式的：C(n, k) * C(k, r)，它等于C(n, r) * C(n - 1, k - 1)。這樣變形之后有一個公共項就可以提出去了，里面還是形如(1 - 1) ^ n的形式。這樣結(jié)果就是0。在計算下一項的系數(shù)的時候，第一次展開后里面恰好包含了前一項的系數(shù)，直接就是0消去了，然后繼續(xù)利用上面的方法展開。中間推導(dǎo)的過程中還需要添加一些值為0的項便于繼續(xù)的推導(dǎo)。
　　這個方法很麻煩，不過推導(dǎo)過程中還是用到了很多知識的，就當(dāng)復(fù)習(xí)了- -!其實這個推導(dǎo)要不是知道了最后的公式也不敢推，實在太麻煩，看來還是基本功欠缺啊，而且算概率的題目還是要多練習(xí)練習(xí)。另外注意思維的靈活性，其實簡單做法不難想，但是最開始被吉大牛誤導(dǎo)了，就用了一個嚴(yán)格的推導(dǎo)方法，獨立思考還是很重要的。

題目代碼：