CF577B Modulo Sum(鹊巢原理,背包)

思路:子序列和是经典的背包问题,但对于这题来说,因为和太大了,需要进一步思考.考虑 m m m很小,应当从这点入手,我们只考虑是否有子序列之和 % m 为 0 \%m为0 %m为0 那么我们考虑对所有的子序列和模 m m m。 此时需要一点灵感,因为即使这样,背包空间是m,物品数量是n,这么做仍然是会超时的.此时,标签中的鹊巢原理就出现作用了,思考,当n>m,时,有大于m件的物品放入m个抽屉中,一定会出现两个值相同的情况,只需取n>n>>m; if(n>m){ cout