1 小时血战无果！
题目链接：link
三次战斗分别：\color{blue}{TLE 30,TLE 45,TLE45}！
都是运用了折半搜索。
第一次代码：
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define i_will signed
#define ak main
#define IMO ()
#define R register
I AK IOI;
int n,a[45],ans;
i_will ak IMO{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int j=1;j<(1<<n);j++){
int sum=0;
vector<int>v;
for(int i=0;i<n;i++){
if(j&(1<<i)){
sum+=a[i];
v.push_back(a[i]);
}
}
if(sum%2!=0) continue;
int t=sum/2,k=v.size();
if(k==0)continue;
int m=k/2;
unordered_map<int,vector<int> >l;
for(int lj=0;lj<(1<<m);lj++){
int s=0;
for(int i=0;i<m;i++)if(lj&(1<<i))s+=v[i];
l[s].push_back(lj);
}
int rr=k-m;
unordered_map<int,vector<int> >r;
for(int rj=0;rj<(1<<rr);rj++){
int s=0;
for(int i=0;i<rr;i++)if(rj&(1<<i))s+=v[m+i];
r[s].push_back(rj);
}
bool flag=0;
int f=(1<<k)-1;
for(auto it:l) {
int tt=t-it.first;
if(r.count(tt)){
auto rj=r[tt];
for(int lj:it.second){
for(int rm:rj){
int c=lj|(rm<<m);
if(c!=0&&c!=f){
flag=1;
goto check;
}
}
}
}
}
check:
if(flag)ans++;
}
cout<<ans;
i_ak ioi;
}
第二次代码：
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define i_will signed
#define ak main
#define IMO ()
#define R register
I AK IOI;namespace BigINT{
#define digit int
#define ull unsigned long long
#define ll long long
class bigInt {digit *value;ull capacity;ull length;bool sign;private:inline void Genshin_Impact_start();inline void emplace_back(const digit &new_digit);inline void put_string(std::string from);inline void put_bigInt(const bigInt &from);inline void put_ull_interger(ull from, const bool &new_sign = 0);inline void put_ll_interger(const ll &from);inline void pop_zero();inline void negation();inline digit at(const int &idx) const;public:void reserve(ull new_cap);bigInt& operator =(const bigInt &from);bigInt& operator =(std::string from);bigInt& operator =(const ull &from);bigInt& operator =(const ll &from);bigInt& operator =(const unsigned int &from);bigInt& operator =(const int &from);bigInt() { Genshin_Impact_start(); }bigInt(std::string str) { put_string(str); }bigInt(const ull &from) { put_ull_interger(from, 0); }bigInt(const ll &from) { put_ll_interger(from); }bigInt(const unsigned int &from) { put_ull_interger(from, 0); }bigInt(const int &from) { put_ll_interger(from); }~bigInt() {delete[] value;}friend std::ostream& operator<<(std::ostream& out, const bigInt &num) {if (num.length == 0) {out << '0';return out;}if (num.sign == 1) out << '-';for (int idx = (num.length) - 1; idx >= 0; --idx) out << char(num.value[idx] + 48);return out;}friend std::istream& operator>>(std::istream& in, bigInt &num) {num.Genshin_Impact_start();char ch = in.get();while (ch < '0' || ch > '9') {if (ch == '-') num.sign = 1;ch = in.get();}while (ch >= '0' && ch <= '9') {num.emplace_back(ch ^ 48);ch = in.get();}for (int l = 0, r = num.length - 1; l < r; ++l, --r) std::swap(num.value[l], num.value[r]);num.pop_zero();return in;}inline ull size();inline ll to_digit();inline std::string to_string();inline bool operator==(const bigInt &other) const;inline bool operator<(const bigInt &other) const;inline bool operator>(const bigInt &other) const;inline bool operator<=(const bigInt &other) const;inline bool operator>=(const bigInt &other) const;inline bool operator!=(const bigInt &other) const;inline bigInt operator<<(const int &num);inline bigInt operator>>(const int &num);inline bigInt operator-() const;inline bigInt operator+(bigInt other);inline bigInt operator-(bigInt other);inline bigInt operator*(bigInt other);inline bigInt operator/(bigInt other);inline bigInt operator%(bigInt other);inline bigInt operator&(bigInt other);inline bigInt operator|(bigInt other);inline bigInt &operator<<=(const int &num);inline bigInt &operator>>=(const int &num);inline bigInt &operator+=(const bigInt &other);inline bigInt &operator-=(const bigInt &other);inline bigInt &operator*=(const bigInt &other);inline bigInt &operator/=(const bigInt &other);inline bigInt &operator%=(const bigInt &other);inline bigInt &operator&=(const bigInt &other);inline bigInt &operator|=(const bigInt &other);bigInt& operator++();bigInt operator++(int);bigInt& operator--();bigInt operator--(int);};inline void bigInt::Genshin_Impact_start() {this->sign = 0;this->capacity = 1;this->length = 0;this->value = new digit[1];this->reserve(-1);}void bigInt::reserve(ull new_cap = -1) {if (new_cap == -1) new_cap = (this->capacity) << 1;digit *past_value = this->value;this->capacity = new_cap;this->value = new digit[this->capacity];for (int idx = 0; idx < (this->length); ++idx) value[idx] = past_value[idx];for (int idx = (this->length); idx < new_cap; ++idx) { value[idx] = 0; }delete[] past_value;}inline void bigInt::put_string(std::string from) {this->Genshin_Impact_start();if (from.front() == '-') {sign = 1;from = from.substr(1);}for (const char &to_put : from) {this->emplace_back(to_put ^ 48);}for (int l = 0, r = this->length - 1; l < r; ++l, --r) std::swap(value[l], value[r]);this->pop_zero();}inline void bigInt::put_bigInt(const bigInt &from) {this->Genshin_Impact_start();for (int idx = 0; idx < from.length; ++idx) this->emplace_back(from.value[idx]);this->sign = from.sign;}inline void bigInt::put_ull_interger(ull from, const bool &new_sign) {this->Genshin_Impact_start();this->sign = new_sign;while (from) {this->emplace_back(from % 10);from /= 10;}this->pop_zero();}inline void bigInt::put_ll_interger(const ll &from) {if (from < 0) this->put_ull_interger((ull)-from, 1);else this->put_ull_interger(from, 0);}inline void bigInt::emplace_back(const digit &new_digit) {if ((this->length) == (this->capacity)) this->reserve();this->value[(this->length)++] = new_digit;}inline void bigInt::pop_zero() {while (length && this->value[length - 1] == 0) {--length;if (length == (capacity >> 1)) reserve(capacity >> 1);}}inline void bigInt::negation() { this->sign = !(this->sign); }inline digit bigInt::at(const int &idx) const {if (idx < length) return value[idx];else return 0;}bigInt &bigInt::operator=(const bigInt &from) { this->put_bigInt(from); return *this; }bigInt &bigInt::operator=(std::string from) { this->put_string(from); return *this; }bigInt &bigInt::operator=(const ull &from) { put_ull_interger(from, 0); return *this; }bigInt &bigInt::operator=(const ll &from) { put_ll_interger(from); return *this; }bigInt &bigInt::operator=(const unsigned int &from) { put_ull_interger(from, 0); return *this; }bigInt &bigInt::operator=(const int &from) { put_ll_interger(from); return *this; }inline ull bigInt::size() { return this->length; }inline ll bigInt::to_digit() {ll ans = 0, weight = 1;for (int i = 0; i < length; ++i) {ans += value[i] * weight;weight *= 10;}return (sign ? (-ans) : ans);}inline std::string bigInt::to_string() {std::string ans;if (sign) ans.push_back('-');for (int i = length - 1; i >= 0; --i) ans.push_back(value[i] + '0');return ans;}inline bool bigInt::operator==(const bigInt &other) const {if (this->length != other.length || this->sign != other.sign) return false;for (int idx = 0; idx < (this->length); ++idx) {if (this->value[idx] != other.value[idx]) return false;}return true;}inline bool bigInt::operator<(const bigInt &other) const {if (this->sign == 1 && other.sign == 0) return true;else if (this->sign == 0 && other.sign == 1) return false;else if (this->sign == 1 && other.sign == 1) return -(*this) > -other;if (this->length < other.length) return true;if (this->length > other.length) return false;for (int idx = (this->length) - 1; idx >= 0; --idx) {if (this->value[idx] > other.value[idx]) return false;if (this->value[idx] < other.value[idx]) return true;}return false;}inline bool bigInt::operator>(const bigInt &other) const {if (this->sign == 1 && other.sign == 0) return false;else if (this->sign == 0 && other.sign == 1) return true;else if (this->sign == 1 && other.sign == 1) return -(*this) < -other;if (this->length > other.length) return true;else if (this->length < other.length) return false;for (int idx = (this->length) - 1; idx >= 0; --idx) {if (this->value[idx] < other.value[idx]) return false;if (this->value[idx] > other.value[idx]) return true;}return false;}inline bool bigInt::operator<=(const bigInt &other) const { return !((*this) > other); }inline bool bigInt::operator>=(const bigInt &other) const { return !((*this) < other); }inline bool bigInt::operator!=(const bigInt &other) const { return !((*this) == other); }inline bigInt bigInt::operator<<(const int &num) {bigInt ans;ans.reserve(length + num);ans.length = ans.capacity;for (int i = 0; i < num; ++i) ans.value[i] = 0;for (int i = 0; i < length; ++i) ans.value[i + num] = value[i];ans.pop_zero();return ans;}inline bigInt bigInt::operator>>(const int &num) {if ((this->length) <= num) return bigInt();bigInt ans;ans.reserve(length - num);ans.length = ans.capacity;for (int i = num; i < length; ++i) ans.value[i - num] = value[i];ans.pop_zero();return ans;}inline bigInt bigInt::operator-() const {bigInt ans = (*this);ans.negation();return ans;}inline bigInt bigInt::operator+(bigInt other) {if (this->sign != other.sign) {if (this->sign == 1) {if (-(*this) > other) return -(-(*this) - other);else return other - (-(*this));}else if (this->sign == 0) {if ((*this) > -other) return (*this) - (-other);else return -(-other - (*this));}}if (other == 0) return (*this);bigInt ans;ans.reserve(std::max(other.length, this->length) + 1);ans.length = ans.capacity;for (int idx = 0; idx < ans.length; ++idx) {ans.value[idx] += this->at(idx) + other.at(idx);if (ans.value[idx] >= 10) {++ans.value[idx + 1];ans.value[idx] -= 10;}}ans.pop_zero();ans.sign = this->sign;return ans;}inline bigInt bigInt::operator-(bigInt other) {if (this->sign || other.sign) {if (this->sign == 0 && other.sign == 1) return (*this) + (-other);if (this->sign == 1) {if (other.sign == 0) {return -(-(*this) + other);}else {return (*this) + (-other);}}}if (other == 0) return (*this);if ((*this) < other) return -(other - (*this));bigInt ans;ans.reserve(this->length);ans.length = ans.capacity;for (int idx = 0; idx < (this->length); ++idx) {ans.value[idx] += this->at(idx) - other.at(idx);if (ans.value[idx] < 0) {--ans.value[idx + 1];ans.value[idx] += 10;}}return ans;}inline bigInt bigInt::operator*(bigInt other) {bigInt ans;int now;ans.reserve(this->length + other.length);ans.length = ans.capacity;for (int idx_this = 0; idx_this < (this->length); ++idx_this) {for (int idx_other = 0; idx_other < other.length; ++idx_other) {now = idx_this + idx_other;ans.value[now] += (this->at(idx_this)) * other.at(idx_other);if (ans.value[now] >= 10) {ans.value[now + 1] += (ans.value[now]) / 10;ans.value[now] %= 10;}}}ans.pop_zero();ans.sign = (this->sign) != other.sign;return ans;}inline bigInt bigInt::operator/(bigInt other) {if (other == bigInt(0)) {std::cerr << "Error: Divide by zero!" << std::endl;throw std::invalid_argument("Divide by zero!");}else if ((*this) == bigInt(0)) return 0;else if ((*this) < other) return 0;bigInt ans, cur, divi = (*this);int l, r, mid;ans.reserve((this->length) - other.length + 1);ans.length = ans.capacity;for (int idx = ans.length - 1; idx >= 0; --idx) {cur = divi >> idx;l = 0, r = 9;while (l < r) {mid = l + r + 1 >> 1;if (other * mid <= cur) l = mid;else r = mid - 1;}mid = l;ans.value[idx] = l;divi = divi - ((other * mid) << idx);divi.pop_zero();}ans.pop_zero();ans.sign = (this->sign) != other.sign;return ans;}inline bigInt bigInt::operator%(bigInt other) {if (other == bigInt(0)) {std::cerr << "Error: Divide by zero!" << std::endl;throw std::invalid_argument("Divide by zero!");}else if ((*this) == bigInt(0)) return 0;bigInt cur, divi = (*this);int l, r, mid;for (int idx = ((this->length) - other.length); idx >= 0; --idx) {cur = divi >> idx;l = 0, r = 9;while (l < r) {mid = l + r + 1 >> 1;if (other * mid <= cur) l = mid;else r = mid - 1;}mid = l;divi = divi - (other * mid << idx);divi.pop_zero();}return divi;}inline bigInt &bigInt::operator<<=(const int &num) { return ((*this) = (*this) << num); }inline bigInt &bigInt::operator>>=(const int &num) { return ((*this) = (*this) >> num); }inline bigInt &bigInt::operator+=(const bigInt &num) { return ((*this) = (*this) + num); }inline bigInt &bigInt::operator-=(const bigInt &num) { return ((*this) = (*this) - num); }inline bigInt &bigInt::operator*=(const bigInt &num) { return ((*this) = (*this) * num); }inline bigInt &bigInt::operator/=(const bigInt &num) { return ((*this) = (*this) / num); }inline bigInt &bigInt::operator%=(const bigInt &num) { return ((*this) = (*this) % num); }inline bigInt bigInt::operator&(bigInt other) {bigInt ans;ans.reserve(std::max(this->length, other.length));ans.length = ans.capacity;for (int i = 0; i < ans.length; ++i) {ans.value[i] = this->at(i) & other.at(i);}ans.pop_zero();ans.sign = this->sign & other.sign;return ans;}inline bigInt bigInt::operator|(bigInt other) {bigInt ans;ans.reserve(std::max(this->length, other.length));ans.length = ans.capacity;for (int i = 0; i < ans.length; ++i) {ans.value[i] = this->at(i) | other.at(i);}ans.pop_zero();ans.sign = this->sign | other.sign;return ans;}inline bigInt &bigInt::operator&=(const bigInt &other) {return (*this = *this & other);}inline bigInt &bigInt::operator|=(const bigInt &other) {return (*this = *this | other);}bigInt& bigInt::operator++() {*this += bigInt(1);return *this;}bigInt bigInt::operator++(int) {bigInt temp = *this;++(*this);return temp;}bigInt& bigInt::operator--() {*this -= bigInt(1);return *this;}bigInt bigInt::operator--(int) {bigInt temp = *this;--(*this);return temp;}
}using namespace BigINT;
namespace fastIO{char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}inline void read(string&s){s="";char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}inline void write(const string&s){for(R int i=0;i<(int)s.size();i++){putchar(s[i]);}}inline void write(const char&c){putchar(c);}
}using namespace fastIO;random_device rd;unsigned int seed=rd()^(chrono::high_resolution_clock::now().time_since_epoch().count());mt19937 gen(seed);inline int rand(const int l,const int r){uniform_int_distribution<>dis(l,r);return dis(gen);}inline int pow(int a,int b){int temp=1;while(b){if(b&1)temp*=a;a*=a;b>>=1;}return temp;}
int n,a[45],ans;
void dfs(int id,int en,int cur,int m,vector<pair<int,int> >&res,vector<int>&v,int t){
if(cur>t)return;
if(id==en){
res.push_back({cur,m});
return;
}
dfs(id+1,en,cur,m,res,v,t);
dfs(id+1,en,cur+v[id],m|(1<<id),res,v,t);
}
i_will ak IMO{
read(n);
for(int i=0;i<n;i++)read(a[i]);
for(int j=1;j<(1<<n);j++){
vector<int>v;
int sum=0;
for(int i=0;i<n;i++){
if(j&(1<<i)){
v.push_back(a[i]);
sum+=a[i];
}
}
if(sum%2!=0||v.empty())continue;
int t=sum/2;
sort(v.begin(),v.end());
int k=v.size();
int m=k/2;
vector<pair<int,int> >l,r;
dfs(0,m,0,0,l,v,t);
dfs(m,k,0,0,r,v,t);
unordered_map<int,vector<int> >r_;
for(auto it:r)r_[it.first].push_back(it.second);
bool flag=0;
int f=(1<<k)-1;
for(auto it:l){
int rr=t-it.first;
if(r_.count(rr)){
for(int rm:r_[rr]){
int c=it.second|(rm<<m);
if(c!=0&&c!=f){
flag=1;
goto check;
}
}
}
}
check:
if(flag)ans++;
}
write(ans);
i_ak ioi;
}
第三次代码：
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define i_will signed
#define ak main
#define IMO ()
#define R register
I AK IOI;namespace BigINT{
#define digit int
#define ull unsigned long long
#define ll long long
class bigInt {digit *value;ull capacity;ull length;bool sign;private:inline void Genshin_Impact_start();inline void emplace_back(const digit &new_digit);inline void put_string(std::string from);inline void put_bigInt(const bigInt &from);inline void put_ull_interger(ull from, const bool &new_sign = 0);inline void put_ll_interger(const ll &from);inline void pop_zero();inline void negation();inline digit at(const int &idx) const;public:void reserve(ull new_cap);bigInt& operator =(const bigInt &from);bigInt& operator =(std::string from);bigInt& operator =(const ull &from);bigInt& operator =(const ll &from);bigInt& operator =(const unsigned int &from);bigInt& operator =(const int &from);bigInt() { Genshin_Impact_start(); }bigInt(std::string str) { put_string(str); }bigInt(const ull &from) { put_ull_interger(from, 0); }bigInt(const ll &from) { put_ll_interger(from); }bigInt(const unsigned int &from) { put_ull_interger(from, 0); }bigInt(const int &from) { put_ll_interger(from); }~bigInt() {delete[] value;}friend std::ostream& operator<<(std::ostream& out, const bigInt &num) {if (num.length == 0) {out << '0';return out;}if (num.sign == 1) out << '-';for (int idx = (num.length) - 1; idx >= 0; --idx) out << char(num.value[idx] + 48);return out;}friend std::istream& operator>>(std::istream& in, bigInt &num) {num.Genshin_Impact_start();char ch = in.get();while (ch < '0' || ch > '9') {if (ch == '-') num.sign = 1;ch = in.get();}while (ch >= '0' && ch <= '9') {num.emplace_back(ch ^ 48);ch = in.get();}for (int l = 0, r = num.length - 1; l < r; ++l, --r) std::swap(num.value[l], num.value[r]);num.pop_zero();return in;}inline ull size();inline ll to_digit();inline std::string to_string();inline bool operator==(const bigInt &other) const;inline bool operator<(const bigInt &other) const;inline bool operator>(const bigInt &other) const;inline bool operator<=(const bigInt &other) const;inline bool operator>=(const bigInt &other) const;inline bool operator!=(const bigInt &other) const;inline bigInt operator<<(const int &num);inline bigInt operator>>(const int &num);inline bigInt operator-() const;inline bigInt operator+(bigInt other);inline bigInt operator-(bigInt other);inline bigInt operator*(bigInt other);inline bigInt operator/(bigInt other);inline bigInt operator%(bigInt other);inline bigInt operator&(bigInt other);inline bigInt operator|(bigInt other);inline bigInt &operator<<=(const int &num);inline bigInt &operator>>=(const int &num);inline bigInt &operator+=(const bigInt &other);inline bigInt &operator-=(const bigInt &other);inline bigInt &operator*=(const bigInt &other);inline bigInt &operator/=(const bigInt &other);inline bigInt &operator%=(const bigInt &other);inline bigInt &operator&=(const bigInt &other);inline bigInt &operator|=(const bigInt &other);bigInt& operator++();bigInt operator++(int);bigInt& operator--();bigInt operator--(int);};inline void bigInt::Genshin_Impact_start() {this->sign = 0;this->capacity = 1;this->length = 0;this->value = new digit[1];this->reserve(-1);}void bigInt::reserve(ull new_cap = -1) {if (new_cap == -1) new_cap = (this->capacity) << 1;digit *past_value = this->value;this->capacity = new_cap;this->value = new digit[this->capacity];for (int idx = 0; idx < (this->length); ++idx) value[idx] = past_value[idx];for (int idx = (this->length); idx < new_cap; ++idx) { value[idx] = 0; }delete[] past_value;}inline void bigInt::put_string(std::string from) {this->Genshin_Impact_start();if (from.front() == '-') {sign = 1;from = from.substr(1);}for (const char &to_put : from) {this->emplace_back(to_put ^ 48);}for (int l = 0, r = this->length - 1; l < r; ++l, --r) std::swap(value[l], value[r]);this->pop_zero();}inline void bigInt::put_bigInt(const bigInt &from) {this->Genshin_Impact_start();for (int idx = 0; idx < from.length; ++idx) this->emplace_back(from.value[idx]);this->sign = from.sign;}inline void bigInt::put_ull_interger(ull from, const bool &new_sign) {this->Genshin_Impact_start();this->sign = new_sign;while (from) {this->emplace_back(from % 10);from /= 10;}this->pop_zero();}inline void bigInt::put_ll_interger(const ll &from) {if (from < 0) this->put_ull_interger((ull)-from, 1);else this->put_ull_interger(from, 0);}inline void bigInt::emplace_back(const digit &new_digit) {if ((this->length) == (this->capacity)) this->reserve();this->value[(this->length)++] = new_digit;}inline void bigInt::pop_zero() {while (length && this->value[length - 1] == 0) {--length;if (length == (capacity >> 1)) reserve(capacity >> 1);}}inline void bigInt::negation() { this->sign = !(this->sign); }inline digit bigInt::at(const int &idx) const {if (idx < length) return value[idx];else return 0;}bigInt &bigInt::operator=(const bigInt &from) { this->put_bigInt(from); return *this; }bigInt &bigInt::operator=(std::string from) { this->put_string(from); return *this; }bigInt &bigInt::operator=(const ull &from) { put_ull_interger(from, 0); return *this; }bigInt &bigInt::operator=(const ll &from) { put_ll_interger(from); return *this; }bigInt &bigInt::operator=(const unsigned int &from) { put_ull_interger(from, 0); return *this; }bigInt &bigInt::operator=(const int &from) { put_ll_interger(from); return *this; }inline ull bigInt::size() { return this->length; }inline ll bigInt::to_digit() {ll ans = 0, weight = 1;for (int i = 0; i < length; ++i) {ans += value[i] * weight;weight *= 10;}return (sign ? (-ans) : ans);}inline std::string bigInt::to_string() {std::string ans;if (sign) ans.push_back('-');for (int i = length - 1; i >= 0; --i) ans.push_back(value[i] + '0');return ans;}inline bool bigInt::operator==(const bigInt &other) const {if (this->length != other.length || this->sign != other.sign) return false;for (int idx = 0; idx < (this->length); ++idx) {if (this->value[idx] != other.value[idx]) return false;}return true;}inline bool bigInt::operator<(const bigInt &other) const {if (this->sign == 1 && other.sign == 0) return true;else if (this->sign == 0 && other.sign == 1) return false;else if (this->sign == 1 && other.sign == 1) return -(*this) > -other;if (this->length < other.length) return true;if (this->length > other.length) return false;for (int idx = (this->length) - 1; idx >= 0; --idx) {if (this->value[idx] > other.value[idx]) return false;if (this->value[idx] < other.value[idx]) return true;}return false;}inline bool bigInt::operator>(const bigInt &other) const {if (this->sign == 1 && other.sign == 0) return false;else if (this->sign == 0 && other.sign == 1) return true;else if (this->sign == 1 && other.sign == 1) return -(*this) < -other;if (this->length > other.length) return true;else if (this->length < other.length) return false;for (int idx = (this->length) - 1; idx >= 0; --idx) {if (this->value[idx] < other.value[idx]) return false;if (this->value[idx] > other.value[idx]) return true;}return false;}inline bool bigInt::operator<=(const bigInt &other) const { return !((*this) > other); }inline bool bigInt::operator>=(const bigInt &other) const { return !((*this) < other); }inline bool bigInt::operator!=(const bigInt &other) const { return !((*this) == other); }inline bigInt bigInt::operator<<(const int &num) {bigInt ans;ans.reserve(length + num);ans.length = ans.capacity;for (int i = 0; i < num; ++i) ans.value[i] = 0;for (int i = 0; i < length; ++i) ans.value[i + num] = value[i];ans.pop_zero();return ans;}inline bigInt bigInt::operator>>(const int &num) {if ((this->length) <= num) return bigInt();bigInt ans;ans.reserve(length - num);ans.length = ans.capacity;for (int i = num; i < length; ++i) ans.value[i - num] = value[i];ans.pop_zero();return ans;}inline bigInt bigInt::operator-() const {bigInt ans = (*this);ans.negation();return ans;}inline bigInt bigInt::operator+(bigInt other) {if (this->sign != other.sign) {if (this->sign == 1) {if (-(*this) > other) return -(-(*this) - other);else return other - (-(*this));}else if (this->sign == 0) {if ((*this) > -other) return (*this) - (-other);else return -(-other - (*this));}}if (other == 0) return (*this);bigInt ans;ans.reserve(std::max(other.length, this->length) + 1);ans.length = ans.capacity;for (int idx = 0; idx < ans.length; ++idx) {ans.value[idx] += this->at(idx) + other.at(idx);if (ans.value[idx] >= 10) {++ans.value[idx + 1];ans.value[idx] -= 10;}}ans.pop_zero();ans.sign = this->sign;return ans;}inline bigInt bigInt::operator-(bigInt other) {if (this->sign || other.sign) {if (this->sign == 0 && other.sign == 1) return (*this) + (-other);if (this->sign == 1) {if (other.sign == 0) {return -(-(*this) + other);}else {return (*this) + (-other);}}}if (other == 0) return (*this);if ((*this) < other) return -(other - (*this));bigInt ans;ans.reserve(this->length);ans.length = ans.capacity;for (int idx = 0; idx < (this->length); ++idx) {ans.value[idx] += this->at(idx) - other.at(idx);if (ans.value[idx] < 0) {--ans.value[idx + 1];ans.value[idx] += 10;}}return ans;}inline bigInt bigInt::operator*(bigInt other) {bigInt ans;int now;ans.reserve(this->length + other.length);ans.length = ans.capacity;for (int idx_this = 0; idx_this < (this->length); ++idx_this) {for (int idx_other = 0; idx_other < other.length; ++idx_other) {now = idx_this + idx_other;ans.value[now] += (this->at(idx_this)) * other.at(idx_other);if (ans.value[now] >= 10) {ans.value[now + 1] += (ans.value[now]) / 10;ans.value[now] %= 10;}}}ans.pop_zero();ans.sign = (this->sign) != other.sign;return ans;}inline bigInt bigInt::operator/(bigInt other) {if (other == bigInt(0)) {std::cerr << "Error: Divide by zero!" << std::endl;throw std::invalid_argument("Divide by zero!");}else if ((*this) == bigInt(0)) return 0;else if ((*this) < other) return 0;bigInt ans, cur, divi = (*this);int l, r, mid;ans.reserve((this->length) - other.length + 1);ans.length = ans.capacity;for (int idx = ans.length - 1; idx >= 0; --idx) {cur = divi >> idx;l = 0, r = 9;while (l < r) {mid = l + r + 1 >> 1;if (other * mid <= cur) l = mid;else r = mid - 1;}mid = l;ans.value[idx] = l;divi = divi - ((other * mid) << idx);divi.pop_zero();}ans.pop_zero();ans.sign = (this->sign) != other.sign;return ans;}inline bigInt bigInt::operator%(bigInt other) {if (other == bigInt(0)) {std::cerr << "Error: Divide by zero!" << std::endl;throw std::invalid_argument("Divide by zero!");}else if ((*this) == bigInt(0)) return 0;bigInt cur, divi = (*this);int l, r, mid;for (int idx = ((this->length) - other.length); idx >= 0; --idx) {cur = divi >> idx;l = 0, r = 9;while (l < r) {mid = l + r + 1 >> 1;if (other * mid <= cur) l = mid;else r = mid - 1;}mid = l;divi = divi - (other * mid << idx);divi.pop_zero();}return divi;}inline bigInt &bigInt::operator<<=(const int &num) { return ((*this) = (*this) << num); }inline bigInt &bigInt::operator>>=(const int &num) { return ((*this) = (*this) >> num); }inline bigInt &bigInt::operator+=(const bigInt &num) { return ((*this) = (*this) + num); }inline bigInt &bigInt::operator-=(const bigInt &num) { return ((*this) = (*this) - num); }inline bigInt &bigInt::operator*=(const bigInt &num) { return ((*this) = (*this) * num); }inline bigInt &bigInt::operator/=(const bigInt &num) { return ((*this) = (*this) / num); }inline bigInt &bigInt::operator%=(const bigInt &num) { return ((*this) = (*this) % num); }inline bigInt bigInt::operator&(bigInt other) {bigInt ans;ans.reserve(std::max(this->length, other.length));ans.length = ans.capacity;for (int i = 0; i < ans.length; ++i) {ans.value[i] = this->at(i) & other.at(i);}ans.pop_zero();ans.sign = this->sign & other.sign;return ans;}inline bigInt bigInt::operator|(bigInt other) {bigInt ans;ans.reserve(std::max(this->length, other.length));ans.length = ans.capacity;for (int i = 0; i < ans.length; ++i) {ans.value[i] = this->at(i) | other.at(i);}ans.pop_zero();ans.sign = this->sign | other.sign;return ans;}inline bigInt &bigInt::operator&=(const bigInt &other) {return (*this = *this & other);}inline bigInt &bigInt::operator|=(const bigInt &other) {return (*this = *this | other);}bigInt& bigInt::operator++() {*this += bigInt(1);return *this;}bigInt bigInt::operator++(int) {bigInt temp = *this;++(*this);return temp;}bigInt& bigInt::operator--() {*this -= bigInt(1);return *this;}bigInt bigInt::operator--(int) {bigInt temp = *this;--(*this);return temp;}
}using namespace BigINT;
namespace fastIO{char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}inline void read(string&s){s="";char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}inline void write(const string&s){for(R int i=0;i<(int)s.size();i++){putchar(s[i]);}}inline void write(const char&c){putchar(c);}
}using namespace fastIO;random_device rd;unsigned int seed=rd()^(chrono::high_resolution_clock::now().time_since_epoch().count());mt19937 gen(seed);inline int rand(const int l,const int r){uniform_int_distribution<>dis(l,r);return dis(gen);}inline int pow(int a,int b){int temp=1;while(b){if(b&1)temp*=a;a*=a;b>>=1;}return temp;}
int n,a[45],ans;
i_will ak IMO{
read(n);
for(int i=0;i<n;i++)read(a[i]);
for(int j=1;j<(1<<n);j++){
vector<int>v;
int sum=0;
for(int i=0;i<n;i++){
if(j&(1<<i)){
v.push_back(a[i]);
sum+=a[i];
}
}
if(sum&1||v.empty())continue;
int t=sum/2;
int maxn=*max_element(v.begin(),v.end());
if(maxn>t)continue;
sort(v.rbegin(),v.rend());
int k=v.size();
int m=k/2;
sort(v.begin(),v.begin()+m,greater<int>());
sort(v.begin()+m,v.end(),greater<int>());
vector<pair<int,int> >l;
for(int lj=0;lj<(1<<m);lj++){
int s=0;
for(int i=0;i<m;i++)if(lj&(1<<i))s+=v[i];
if(s<=t)l.push_back({s,lj});
}
int rr=k-m;
unordered_map<int,vector<int> >r;
for(int rj=0;rj<(1<<rr);rj++){
int s=0;
for(int i=0;i<rr;i++)if(rj&(1<<i))s+=v[m+i];
if(s<=t)r[s].push_back(rj);
}
bool flag=0;
int f=(1<<k)-1;
for(auto it:l){
int r_=t-it.first;
if(r.count(r_)){
for(int rm:r[r_]){
int c=it.second|(rm<<m);
if(c!=0&&c!=f){
flag=1;
goto check;
}
}
}
}
check:
if(flag)ans++;
}
write(ans);
i_ak ioi;
}
后面代码用了快读快写，想要测样例在最后加上 ctrl+Z 即可。
