#include <bits/stdc++.h> using namespace std; const int nax = 5001; constexpr int mod = 1e9 + 7; int res[nax]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int &i : a) { cin >> i; } res[0] = 1; sort(a.begin(), a.end()); for (int x : a) { for (int i = nax - 1; i >= x - 1; --i) { int j = min(i + x, nax); res[j] = (res[j] + res[i]) % mod; } } int sum = 0; for (int i = 1; i < nax; ++i) { sum = (sum + res[i]) % mod; } cout << sum << "\n"; }
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 | #include <bits/stdc++.h> using namespace std; const int nax = 5001; constexpr int mod = 1e9 + 7; int res[nax]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int &i : a) { cin >> i; } res[0] = 1; sort(a.begin(), a.end()); for (int x : a) { for (int i = nax - 1; i >= x - 1; --i) { int j = min(i + x, nax); res[j] = (res[j] + res[i]) % mod; } } int sum = 0; for (int i = 1; i < nax; ++i) { sum = (sum + res[i]) % mod; } cout << sum << "\n"; } |