D - Happy Birthday! 2
题意
给定一个序列，找出是否存在两个不同的子序列，子序列的总和对\(200\)同余。
解题
一个直接的想法就是将所有可能的情况都遍历一边，如果我们使用最暴力的方法，枚举每个元素所在组的情况，时间复杂度将会非常高，因此我们需要另外的解法。考虑到子序列求和后需要对\(200\)求余，也就是说我们得到的余数结果的范围在\([0,200)\)之间。题目要求出一对子序列，也就是说总和求余后是一样的。
这里我们可以根据抽屉原理，知道如果我们计算过\(201\)个子序列后，就必定存在两个子序列的总和是同余的。抽屉原理也叫鸽洞原理，简单举个例子就是假设有\(200\)个鸽子洞，但是我们有\(201\)个鸽子需要回到洞里，那么就必定存在一个洞中有两只鸽子。
在本题中，对总和求余的所有可能就是例子中的\(200\)个鸽子洞，当我们有超过\(200\)个子序列的时候，我们就可以得到超过\(200\)种可能的求余结果，因此就必定存在两个子序列的求余结果是相同的。同时，对于\(N\)个元素，我们可以得到的可能子序列个数为\(2^N-1\)个，当\(N\ge 8\)时，就一定会有结果，而当\(N\le 8\)时，需要判断是否存在结果。
综上，我们只需要\(\min(n,8)\)个元素，再利用二进制枚举子序列，最后找到相同余数的子序列就得到结果，如果不存在就输出\(No\);
参考代码
点此展开
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void print(vector<int> arr){
cout<<arr.size();
for(auto c:arr){
cout<<" "<<c;
}
cout<<endl;
}
int main()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0; i<n; i++) cin>>a[i];
int cnt=min(8,n);
vector<int> rem[201];
for(int i=1;i<1<<cnt;i++){
int seg=0;//记录总和得到的余数
vector<int> tmp;//记录子序列
for(int j=0;j<cnt;j++){
if(i&(1<<j)){
tmp.push_back(j+1);
seg+=a[j];
seg%=200;
}
}
if(rem[seg].size()!=0){//此前已经有过同样余数的子序列
cout<<"Yes"<<endl;
print(rem[seg]);
print(tmp);
return 0;
}
else
{
rem[seg]=tmp;
}
}
cout<<"No"<<endl;
return 0;
}