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

题目代码：
【题目大意】
　　题目的大意是给定一个由许多六面形边挨着边组成的图形，从中心处开始标号为1，按照一个螺旋的方向标号依次增加。问从一个点到另一个点的最短路径的长度和数目。

【算法分析】
　　感觉满恶心的一个题目，需要疯狂的找规律。首先容易看出路径数是一个组合数，并且每一层都是模六循环的。但是怎样找到层数（也就是最短路径长度）呢？最开始想建立坐标系然后利用几何方法算出来，但是如何无论是笛卡尔坐标系还是极坐标系的建立都是困难的；然后想存图广搜，发现空间不够。后来发现，把图顺时针转90度，出现了一个很有意思的规律。以原点（数字为1）为中心建立坐标系，不过坐标的选取需要一些技巧。可以看出数字是一层层分布的，取x左边的点坐标为（-2，0），以后每往左增加一层，横坐标就变化2。其实和原点纵坐标相同且位于其左边的点恰好是每一层数字最大的结点！这样只要确定了这个点，可以按照逆时针的顺序依次给这一层的所有点的坐标推出来。这样，给定一个数字，我们可以根据每一层最大的数字推出这个数的坐标。
　　现在有了坐标（可以看成是曼哈顿坐标），就可以推测路径了。把两个数字的坐标求差，就可以看成是一个在原点了。坐标和路径的关系不是很好找，写了4、5行发现了一个很诡异的规律。先把坐标化成正的，然后发现x >= y的时候就是C( (x + y) / 2, y)，否则是C( y, (y - x) / 2)。之后就是高精度了。

题目代码：



　　很有意思的题目，给定一个数（长达500000位），问它是不是一个数n的n次幂，如果是，输出n，否则输出-1。还有一个条件是如果不是的话，它只可能有一位写错了，而且数的位数不变。
　　首先考虑如果确定n，当n大于1的时候，n ^ n的位数是不同的(n * logn)，这样根据输入的长度可以确定n。之后就要考虑怎样检测出这个数是不是正确的。因为只有一位可能有变换，那么就是在原数的基础上多了（或少了）一个k * 10 ^ i，其中k = 1...9，i = 0...n。考察这个数的素因子，只可能是2、3、5、7，这样的话如果我取一个模11，显然k * 10 ^ i模11的值一定不为0，这样的话如果有一位发生了变化，它模11的结果和n ^ n模11的结果肯定不同，根据这个方法我就可以在O(L)的复杂度内检测出这个数是否正确了，L是位数。
　　实现的时候有一个很容易出错的地方。因为需要预处理出每个n的n次幂的位数，正常的话n * logn向上取整就是答案，但是n是10的整数幂的时候有些特别，是n * logn + 1，需要单独处理（我是加了一个1e-2再向上取整），因为这个原因错了一次，还有一次是输入的字符串大小开小了。
附题目代码：
　　一个经典的问题：给定n个数，求其中的任意一个子集满足集合中的每个元素值加和正好是n的倍数。刚开始怎么也没有思路，因为n很大，直接搜索显然是不行的。后来在组合数学书上找到了这个例题（晕，之前白看了，居然把这个经典的题目都给忘了），是抽屉原理的典型应用。
　　假定n个数为a1，a2，...，an，前n项和分别是S1、S2、...、Sn，那么如果有一个Si模n是0，就是答案，否则，n个数模n的余数只能在1到n - 1之间，把余数作为抽屉，显然n个数放到n - 1个抽屉里面，肯定有两个数余数相等，这样取它们的差就得到了结果，算法复杂度是O(n)的。
　　抽屉原理的应用都十分巧妙。还有一个例子，一个屋子里面有n个人，他们的最大年龄不超过k岁，问是否肯定存在2组人（两组没有重复的人），使得这两组人的年龄和相等。n个人的组合一共有2 ^ n种方法，注意到最大情况n的人的年龄和是n * k，这样如果2 ^ n > n * k，根据抽屉原理，一定存在两种组合他们的年龄和相等，而且没有重复的人（如果重复，把那个人删去就行了）。所以O(1)的时间就判断出了结果。
　　不过在最开始做题目（PKU 2356）的时候，虽然代码很短，但是错了好多次。首先是数组开小了，然后发现输出的时候题目要求的是输出数但是我给输出下标了。最后的问题出在一个很关键的地方，在取模为零的时候，我本应该直接就记录产生了解，但是我以为取模为零的时候下次肯定会产生重复的标记，就没有特殊处理。其实如果第一个数取模就是0的话，就有可能后面不产生重复的标记，这样我的程序就错了，还有就是最后一个是取模为零的时候也会出问题。想了很久才想到这个问题，改正之后终于过了。以后写程序要仔细，不能想当然啊。
附PKU 2356代码：

 　　这个题目做得好辛苦。题目大意是给三个算术表达式，前两个相加等于第三个，每位数都用字母代替，问最后字母对应的数是多少。数据范围n <= 26。由于进位不确定，因此需要枚举进位，再用高斯消元求解。我报着试一试的态度敲了一个2 ^ n * n ^ 3的程序上去，果然超时了。不知道应该如何优化，到网上看了一下，因为每次枚举的都是常数，因此可以先把每个未知数用常量表示出来，这样每次枚举回带求解的复杂度就降到了O(n ^ 2)。感觉这种做法很巧妙，不过实现的时候出了很多问题，搞了一下午才搞定- -!
　　首先需要保存对于每个变量，它对应的每个常数的系数是多少。开始的时候我列方程的方向想错了，相当成模n域的方程组来求解。结果写了很久之后发现因为n不一定是素数，所以求解的时候解可能有多个，这样的话就比较复杂了。后来一怒之下索性当成实数域来求解，重新列了方程，这样解就是唯一的了，但是中间运算全是浮点数，很担心精度问题，交上去居然过了。
　　这个题目加速消元的思想还是很值得借鉴的，高斯消元的优化问题不多，但是感觉都挺有意思，就像用弦图加速高斯消元。根据方程的不同特点来选择合适的优化方法很重要啊。