本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-18 11:18:38

题解：[ABC200D] Happy Birthday! 2

最朴素、最暴力的做法是枚举 $N$ 的全排列，但是因为有 $ N \le 200$，所以这种方法无疑会超时。

这时候我们可以用容斥的思路进行优化。引入抽屉原理：

将 $n+1$ 个物体，划分为 $n$ 组，那么有至少一组有两个（或以上）的物体。

因为模数是 200，所以我们只要有 201 个互异的序列，就一定会有两个序列的和同余。而对于长度为 $N$ 的序列，我们可以构造出 $2^N$ 种不同序列。对于 $N\le8$，我们可以暴力取得答案；而对于 $N>8$，因为 $2^8=256>200$，所以一定有答案，我们只需要用前八个元素构造序列，然后用桶存储和判断即可。

代码如下：

#include<bits\/stdc++.h>
#include<vector>
#include<map>
using namespace std;
#define int long long
#define F(i,l,r) for(int i = l;i <= r;i++)

int n,a[205];
map<int,vector<int> > mp;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n;
	F(i,1,n){
		cin>>a[i];
		a[i]%=200;
	}
	n=min(n,8ll);
	for(int i=1;i<1<<n;i++){
		vector <int> t;
		int sum=0;
		for(int j=1;j<=n;j++){
			if(i>>(j-1) & 1){
				t.push_back(j);
				sum=(sum+a[j])%200;
			}
		}
		sum%=200;
		if(mp.find(sum)!=mp.end()){
			cout<<"Yes\n"<<mp[sum].size()<<' ';
			for(auto e:mp[sum])	cout<<e<<' ';
			cout<<'\n'<<t.size()<<' ';
			for(auto e:t) cout<<e<<' ';
			return 0;
		}
		mp[sum]=t;
	}
	cout<<"No\n";

	return 0;
}

$2024.9.18$ 完稿