題目大意就是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不一定是素數，所以求解的時候解可能有多個，這樣的話就比較復雜了。后來一怒之下索性當成實數域來求解，重新列了方程，這樣解就是唯一的了，但是中間運算全是浮點數，很擔心精度問題，交上去居然過了。
　　這個題目加速消元的思想還是很值得借鑒的，高斯消元的優化問題不多，但是感覺都挺有意思，就像用弦圖加速高斯消元。根據方程的不同特點來選擇合適的優化方法很重要啊。