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

題目代碼：