思路:子序列和是经典的背包问题,但对于这题来说,因为和太大了,需要进一步思考.考虑
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
关注
打赏
查看更多评论
