一個經(jīng)典的問題：給定n個數(shù)，求其中的任意一個子集滿足集合中的每個元素值加和正好是n的倍數(shù)。剛開始怎么也沒有思路，因為n很大，直接搜索顯然是不行的。后來在組合數(shù)學(xué)書上找到了這個例題（暈，之前白看了，居然把這個經(jīng)典的題目都給忘了），是抽屜原理的典型應(yīng)用。
　　假定n個數(shù)為a1，a2，...，an，前n項和分別是S1、S2、...、Sn，那么如果有一個Si模n是0，就是答案，否則，n個數(shù)模n的余數(shù)只能在1到n - 1之間，把余數(shù)作為抽屜，顯然n個數(shù)放到n - 1個抽屜里面，肯定有兩個數(shù)余數(shù)相等，這樣取它們的差就得到了結(jié)果，算法復(fù)雜度是O(n)的。
　　抽屜原理的應(yīng)用都十分巧妙。還有一個例子，一個屋子里面有n個人，他們的最大年齡不超過k歲，問是否肯定存在2組人（兩組沒有重復(fù)的人），使得這兩組人的年齡和相等。n個人的組合一共有2 ^ n種方法，注意到最大情況n的人的年齡和是n * k，這樣如果2 ^ n > n * k，根據(jù)抽屜原理，一定存在兩種組合他們的年齡和相等，而且沒有重復(fù)的人（如果重復(fù)，把那個人刪去就行了）。所以O(shè)(1)的時間就判斷出了結(jié)果。
　　不過在最開始做題目（PKU 2356）的時候，雖然代碼很短，但是錯了好多次。首先是數(shù)組開小了，然后發(fā)現(xiàn)輸出的時候題目要求的是輸出數(shù)但是我給輸出下標(biāo)了。最后的問題出在一個很關(guān)鍵的地方，在取模為零的時候，我本應(yīng)該直接就記錄產(chǎn)生了解，但是我以為取模為零的時候下次肯定會產(chǎn)生重復(fù)的標(biāo)記，就沒有特殊處理。其實如果第一個數(shù)取模就是0的話，就有可能后面不產(chǎn)生重復(fù)的標(biāo)記，這樣我的程序就錯了，還有就是最后一個是取模為零的時候也會出問題。想了很久才想到這個問題，改正之后終于過了。以后寫程序要仔細(xì)，不能想當(dāng)然啊。
附PKU 2356代碼：