Timus练习

Published: by Creative Commons Licence

  • Tags:

TIMUS1032

题意

http://acm.timus.ru/problem.aspx?space=1&num=1032

题解

组合数学书上一道用于介绍鸽巢定理的例题。如果以前没看过,我应该也做不出来。

首先给出n个值a1,a1+a2,…,a1+a2+…+an,如果其中有一个模n为0,那么就找到了解。否则由于有n个值落在1~n-1之间,因此至少有两个数有相同值,找到这两个数,其中一个必定是另外一个的前缀,从较长的序列中移除较短的序列那部分就找到解了。