POJ 2356 Find a multiple (dp + 鴿籠原理)

oj題目：

題目分析：n個數，從中取若幹個數，和為n的倍數。給出一種取法。

因為隻要給出其中一種方案就行，鴿籠原理可以求出取出的數為連續的方案。

關于鴿籠原理，

直接貼過來：

有n+1件或n+1件以上的物品要放到n個抽屜中，那麼至少有一個抽屜裡有兩個或兩個以上物品。

如果你知道這個結論：

a1,a2,a3...am是正整數序列，至少存在整數k和r,1<=k<r<=m,使得ak+a(k+1)+...+a(r)是m的倍數。

證明比較簡單:

sk表示前k個數之和，

 (1)若sk%m==0,前k個數就是m的倍數

（2）如果sn與st模m同餘，那麼從t+1到n這些數之和模m等于0.

即使你不知道這個結論，dp厲害的話，應該能想到用 前n項的和 去思考的思想

有這個結論知必有解。

貼代碼之前，在總結一下鴿籠原理的結論：

推論1：m隻鴿子，n個籠，則至少有一個鴿籠裡有不少于[(m-1)/n]+1隻鴿子。

推論2:若取n*(m-1)+1個球放進n個盒子，則至少有1個盒子有m個球。

推論3：若m1,m2,...mn是n個正整數，而且（m1+m2+...+mn）/n>r-1

則m1,m2,...mn中至少有一個數不小于r

ac_code