题解:[ABC200D] Happy Birthday! 2

· · 题解

题解：[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;
}