题解：AT_abc200_d [ABC200D] Happy Birthday! 2

Steady_Steve · 2025-11-15 15:37:36 · 题解

算法：抽屉原理，状态压缩

解题思路：

抽屉原理先加证明：显而易见，在 201 个序列中必定有两个对 200 取模的余数相同。

因为 2^8=256>200，所以我们只需要状态压缩枚举前 8 个数列的情况总数，找到即输出。

当 n \ge 9 时，上述情况同 n \le 8， 一定有解。

• 用 vector 存储状态压缩的情况，满足直接输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[2001];
vector<int>f[2001];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]%=200;
    }
    if(n>8) n=8;
    for(int i=0;i<(1<<n);i++){
        vector<int>v;
        int s=0;
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                s=(s+a[j])%200;
                v.push_back(j+1);
            }
        }
        if(f[s].size()){
            puts("Yes");
            cout<<f[s].size()<<" ";
            for(auto x:f[s]) cout<<x<<" ";
            puts("");
            cout<<v.size()<<" ";
            for(auto x:v) cout<<x<<" ";
            exit(0);
        }
        f[s]=v;
    }
    puts("No");

    return 0;
}