题目大意就是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的项便于继续的推导。
　　这个方法很麻烦，不过推导过程中还是用到了很多知识的，就当复习了- -!其实这个推导要不是知道了最后的公式也不敢推，实在太麻烦，看来还是基本功欠缺啊，而且算概率的题目还是要多练习练习。另外注意思维的灵活性，其实简单做法不难想，但是最开始被吉大牛误导了，就用了一个严格的推导方法，独立思考还是很重要的。

题目代码：