//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <atcoder/convolution>
#include <atcoder/modint>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define lc v << 1
#define rc (v << 1) + 1
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef complex<double> cd;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }
const double PI = acos(-1);
void fft(vector<cd> & a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;
if (i < j)
swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1, 0);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd & x : a)
x /= n;
}
}
vector<int> multiply(vector<int> const& a, vector<int> const& b) {
vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while (n < sz(a) + sz(b))
n <<= 1;
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; i++)
fa[i] *= fb[i];
fft(fa, true);
vector<int> result(n);
for (int i = 0; i < n; i++)
result[i] = round(fa[i].real());
return result;
}
const int BASE = 270;
const int MX = BASE * BASE + 1;
using bts = bitset<MX>;
int last_bit(bts& a) {
int i = a._Find_first();
while(a._Find_next(i) != sz(a))
i = a._Find_next(i);
return i;
}
bts sum(bts& a, bts& b) {
int al = last_bit(a), bl = last_bit(b);
vi v1, v2;
forn(i, al + 1)
v1.pb(a[i]);
forn(i, bl + 1)
v2.pb(b[i]);
vi c = multiply(v1, v2);
bts res;
forn(i, min(sz(c), MX))
if(c[i] > 0)
res[i] = 1;
return res;
}
int pr1 = 2011;
int pr2 = 1000 * 1000 * 1000 + 7;
int add(int a, int b, int mod) {
return ((a + b) % mod + mod) % mod;
}
bts divide(vi pol1, vi pol2, int d) {
bts res;
for(int i = 0; i + d < MX; i++) {
if(pol1[i] != 0 || pol2[i] != 0) {
pol1[i + d] = add(pol1[i + d], -pol1[i], pr1);
pol2[i + d] = add(pol2[i + d], -pol2[i], pr2);
res[i] = 1;
}
}
return res;
}
void solve() {
int n;
cin >> n;
vi arr(n);
forn(i, n)
cin >> arr[i];
sort(all(arr));
vi pol1(MX, 0);
pol1[0] = 1;
for(int a: arr) {
for(int i = MX - a - 1; i >= 0; i--) {
pol1[i + a] = add(pol1[i + a], pol1[i], pr1);
}
}
vi pol2(MX, 0);
pol2[0] = 1;
for(int a: arr) {
for(int i = MX - a - 1; i >= 0; i--) {
pol2[i + a] = add(pol2[i + a], pol2[i], pr2);
}
}
bts s;
s[0] = 1;
int total = 0;
bool odd = true, even = true;
for(int a: arr) {
s |= s << a;
total += a;
if(a % 2)
even = false;
else
odd = false;
}
if(total % 2 || s[total / 2] == 0 || (!even && !odd))
{
cout << -1;
return;
}
bts ans;
ans.flip();
forn(i, n) {
bts c = divide(pol1, pol2, arr[i]);
int d = (total - arr[i] - (odd ? 1 : 0)) / 2;
ans &= c >> d;
}
vi vans;
forbn(i, 1, MX) {
if(ans[i]) {
vans.pb(2 * i - (odd ? 1 : 0));
}
}
cout << sz(vans) << '\n';
for(int el: vans)
cout << el << ' ';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("triangles.in", "r", stdin);
// freopen("triangles.out", "w", stdout);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
Compilation message
bootfall.cpp:3:10: fatal error: atcoder/convolution: No such file or directory
3 | #include <atcoder/convolution>
| ^~~~~~~~~~~~~~~~~~~~~
compilation terminated.
