#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vl; typedef vector<vector<ll>> vvl; #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define st first #define nd second #define FOR(__VAR, __START, __END) for(int __VAR=__START; __VAR<=__END; __VAR++) #define FORB(__VAR, __START, __END) for(int __VAR=__START; __VAR>=__END; __VAR--) #define FORK(__VAR, __START, __END, __DIFF) for(int __VAR=__START; __VAR<=END; __VAR+=__DIFF) #define all(__VAR) (__VAR).begin(), (__VAR).end() #define rall(__VAR) (__VAR).rbegin(), (__VAR).rend() #define DEBUG(__VAR) cout << #__VAR << ": " << __VAR << endl; template<typename __T1, typename __T2> ostream & operator<<(ostream &out, pair<__T1, __T2> &__VAR) { cout << "[" << __VAR.st << ", " << __VAR.nd << "]"; return out; } template<typename __T> ostream & operator<<(ostream &out, vector<__T> &__VAR) { cout << "["; FOR(i, 0, (int)__VAR.size()-2) cout << __VAR[i] << ", "; if(__VAR.size()>0) cout << __VAR[__VAR.size()-1]; cout << "]" << endl; return out; } const ll INF=1e9, MAXN=5000, MOD=1e9+7; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector<int> v(n); for(int i=0; i<n; i++) cin >> v[i]; sort(v.begin(), v.end()); vector<ll> dp(MAXN+1, 0); dp[0]=1LL; for(ll val:v) { dp[MAXN]=(2*dp[MAXN])%MOD; for(int i=MAXN-1; i>=(val-1); i--) dp[min(MAXN,i+val)]=(dp[min(MAXN,i+val)]+dp[i])%MOD; } ll result=0; for(ll res:dp) result+=res; result=(result+MOD-1LL)%MOD; cout << result << '\n'; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vl; typedef vector<vector<ll>> vvl; #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define st first #define nd second #define FOR(__VAR, __START, __END) for(int __VAR=__START; __VAR<=__END; __VAR++) #define FORB(__VAR, __START, __END) for(int __VAR=__START; __VAR>=__END; __VAR--) #define FORK(__VAR, __START, __END, __DIFF) for(int __VAR=__START; __VAR<=END; __VAR+=__DIFF) #define all(__VAR) (__VAR).begin(), (__VAR).end() #define rall(__VAR) (__VAR).rbegin(), (__VAR).rend() #define DEBUG(__VAR) cout << #__VAR << ": " << __VAR << endl; template<typename __T1, typename __T2> ostream & operator<<(ostream &out, pair<__T1, __T2> &__VAR) { cout << "[" << __VAR.st << ", " << __VAR.nd << "]"; return out; } template<typename __T> ostream & operator<<(ostream &out, vector<__T> &__VAR) { cout << "["; FOR(i, 0, (int)__VAR.size()-2) cout << __VAR[i] << ", "; if(__VAR.size()>0) cout << __VAR[__VAR.size()-1]; cout << "]" << endl; return out; } const ll INF=1e9, MAXN=5000, MOD=1e9+7; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector<int> v(n); for(int i=0; i<n; i++) cin >> v[i]; sort(v.begin(), v.end()); vector<ll> dp(MAXN+1, 0); dp[0]=1LL; for(ll val:v) { dp[MAXN]=(2*dp[MAXN])%MOD; for(int i=MAXN-1; i>=(val-1); i--) dp[min(MAXN,i+val)]=(dp[min(MAXN,i+val)]+dp[i])%MOD; } ll result=0; for(ll res:dp) result+=res; result=(result+MOD-1LL)%MOD; cout << result << '\n'; return 0; } |