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

題目代碼：