Poj 3370 Halloween treats

這道題在集訓手冊上標志是“抽屜原理”，老實說，在看到這道題的具體解法之前，我還不知道為什么是抽屜原理，這明明是判斷一些數的同余嘛，后來才發(fā)現鴿籠原理的巧妙之處。

 

4 5

1 2 3 7 5

 

例如對于第一組數據，

1 2 3 7 5模上4分別是：

1 2 3 3 1

如果采用同余+dp的方法，難度會相當大，規(guī)則比較復雜；

 

這時，我們采用一種巧妙地方法，就是用一個sum[i]數組來記錄前i個數之和%4，例如上例中，我們得到：

I	0(該列隱含)	1	2	3	4	5
Sweet[i]	0	1	2	3	7	5
Sum[i]	0	1	3	2	1	2

 

由此，我們在碰到1.sum[i] == 0 或者2.sum[i]的值已經在前面出現過的情況時，就可以知道有解，并且解是從上一個出現該sum[i]數值的后一個位置開始→現在sum[i]的位置，這個貌似可以解出可能的解；但由于加和的順序隨機，所以還不清楚是否可以在該case有解的情況下一定能夠解出解。這時候，我們就要用到鴿籠原理了。

 

運用《離散數學與組合數學》書中的方法，我們可以把sum[1~n=nneighbor](或0~n)看做n+1只鴿子（注意上面的隱含0列），飛入c=nchild個鴿籠中，再注意到題目中有這樣的數據范圍：

The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000) （這是本題能用鴿籠原理的最重要的前提）

由此我們可以知道一定有兩只鴿子是飛入同一個籠子當中的，所以加法的順序就自然不用考慮了；而且由這個我們也可以知道，此題一定不存在無解的情況。

代碼就不貼了，數學題還是要自己想才好