传送门
我们可以看出,B©序列的所有情况一共有2^n - 1种(就是每个数取或者不取),直接枚举肯定是不行。
再继续观察题目给出的条件,求和后要对200取模,也就是说取模后的结果有200种情况。我们所有序列的情况一共2^n - 1种,取极限情况,当前200种情况所得的结果都不相同时,第201种情况必定出现重复,因此只要情况总数超过200时必定有解。我们可以取n = 8(2 ^ 8-1 > 201)然后找到两种相同的情况即可。当n < 8 时,我们也可以采用同样的方法枚举。
不知道为什么开200的时候会越界,开300的时候就不会了。。。。。
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int, int> P;const int maxn = 200 + 10;
const int M_MAX = 10;
const int mod = 1e9 + 7;
const LL INF = 0x3f3f3f3f;
const double eps = 1e-6; int n;
int arr[maxn];
vector<int> ans[300];void out(vector<int> &t) {cout << t.size();for(auto i : t) {cout << " " << i;}cout << endl;
}void solve() {cin >> n;for(int i = 0; i < n; i++) cin >> arr[i];int cnt = min(n, 8);for(int i = 0; i < 1 << cnt; i++) {LL sum = 0;vector<int> s;for(int j = 0; j < cnt; j++) {if(1 << j & i) {s.emplace_back(j + 1);sum += arr[j];}}sum %= 200;if(!ans[sum].empty()) {cout << "YES\n";out(ans[sum]);out(s);return ;}else {ans[sum] = s;}}cout << "NO\n";
}int main() {ios::sync_with_stdio(false);//srand(time(NULL)); //更新种子solve();return 0;
}