#include <bits/stdc++.h> using namespace std; #define endl "\n" #define mp make_pair #define st first #define nd second #define pii pair<int, int> #define pb push_back #define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0); #define REP(i, n) for (int i = 0; i < (n); ++i) #define FWD(i, a, b) for (int i = (a); i < (b); ++i) #define rep(i, n) for (int i = 0; i < (n); ++i) #define fwd(i, a, b) for (int i = (a); i < (b); ++i) #define all(c) (c).begin(), (c).end() #define sz(X) (int)((X).size()) #define what(x) cerr << #x << " is " << x << endl; #define int long long const int MOD = 1e9 + 7; const int MAXM = 1e4; int tab[MAXM + 10]; int32_t main() { _upgrade; int n; cin >> n; vector<int> X(n); rep(i, n) cin >> X[i]; sort(all(X)); tab[0] = 1; for (int a : X) { for (int l = MAXM; l >= a - 1; l--) tab[min(l + a, MAXM)] = (tab[min(l + a, MAXM)] + tab[l]) % MOD; } int res = accumulate(tab + 1, tab + MAXM + 1, 0ll); cout << res % MOD << endl; }
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 | #include <bits/stdc++.h> using namespace std; #define endl "\n" #define mp make_pair #define st first #define nd second #define pii pair<int, int> #define pb push_back #define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0); #define REP(i, n) for (int i = 0; i < (n); ++i) #define FWD(i, a, b) for (int i = (a); i < (b); ++i) #define rep(i, n) for (int i = 0; i < (n); ++i) #define fwd(i, a, b) for (int i = (a); i < (b); ++i) #define all(c) (c).begin(), (c).end() #define sz(X) (int)((X).size()) #define what(x) cerr << #x << " is " << x << endl; #define int long long const int MOD = 1e9 + 7; const int MAXM = 1e4; int tab[MAXM + 10]; int32_t main() { _upgrade; int n; cin >> n; vector<int> X(n); rep(i, n) cin >> X[i]; sort(all(X)); tab[0] = 1; for (int a : X) { for (int l = MAXM; l >= a - 1; l--) tab[min(l + a, MAXM)] = (tab[min(l + a, MAXM)] + tab[l]) % MOD; } int res = accumulate(tab + 1, tab + MAXM + 1, 0ll); cout << res % MOD << endl; } |