#include <bits/stdc++.h> using namespace std; using ll = long long; const int mod = 1'000'000'007; const int maxa = 5010; ll p2[5010]; int main() { int n; scanf("%d", &n); p2[0] = 1; vector<int> arr(n); for (int i = 0; i < n; i++) { p2[i+1] = (p2[i] * 2) % mod; scanf("%d", &arr[i]); } sort(arr.begin(), arr.end()); // int maxa = arr.back() + 2; vector<ll> dp(2 * maxa + 1), dpb(2 * maxa); dp[0] = 1; dpb[0] = 1; int max_ok = 0; int i = 0; for (; i < n; i++) { if (arr[i] > max_ok + 1) { while (n > i) { arr.pop_back(); n--; } break; } dp[2*maxa] = (2 * dp[2*maxa]) % mod; for (int j = 2 * maxa - 1; j >= arr[i] - 1; j--) { int jj = min(j + arr[i], 2 * maxa); dp[jj] = (dp[jj] + dp[j]) % mod; dpb[jj] |= dpb[j]; if (dpb[jj]) { max_ok = max(max_ok, jj); } } // for (int k = 0; k < min((int)dp.size(), 30); k++) printf("%lld(%d) ", dp[k], k); printf("\n"); // if (arr[i] * 2 > min(max_ok, maxa) && max_ok > maxa) { // i++; // break; // } } // for (int k = 0; k < maxa; k++) printf("%d ", dp[k]); printf("\n"); for (int k = 2 * maxa - 1; k >= 0; k--) { dp[k] = (dp[k] + dp[k+1]) % mod; } ll res = dp[1]; for (; i < n; i++) { // printf("%d %lld %lld\n", i, p2[n-i-1], dp[arr[i]-1]); res = (res + p2[n - i - 1] * dp[arr[i]-1]) % mod; } printf("%lld\n", res); }
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 | #include <bits/stdc++.h> using namespace std; using ll = long long; const int mod = 1'000'000'007; const int maxa = 5010; ll p2[5010]; int main() { int n; scanf("%d", &n); p2[0] = 1; vector<int> arr(n); for (int i = 0; i < n; i++) { p2[i+1] = (p2[i] * 2) % mod; scanf("%d", &arr[i]); } sort(arr.begin(), arr.end()); // int maxa = arr.back() + 2; vector<ll> dp(2 * maxa + 1), dpb(2 * maxa); dp[0] = 1; dpb[0] = 1; int max_ok = 0; int i = 0; for (; i < n; i++) { if (arr[i] > max_ok + 1) { while (n > i) { arr.pop_back(); n--; } break; } dp[2*maxa] = (2 * dp[2*maxa]) % mod; for (int j = 2 * maxa - 1; j >= arr[i] - 1; j--) { int jj = min(j + arr[i], 2 * maxa); dp[jj] = (dp[jj] + dp[j]) % mod; dpb[jj] |= dpb[j]; if (dpb[jj]) { max_ok = max(max_ok, jj); } } // for (int k = 0; k < min((int)dp.size(), 30); k++) printf("%lld(%d) ", dp[k], k); printf("\n"); // if (arr[i] * 2 > min(max_ok, maxa) && max_ok > maxa) { // i++; // break; // } } // for (int k = 0; k < maxa; k++) printf("%d ", dp[k]); printf("\n"); for (int k = 2 * maxa - 1; k >= 0; k--) { dp[k] = (dp[k] + dp[k+1]) % mod; } ll res = dp[1]; for (; i < n; i++) { // printf("%d %lld %lld\n", i, p2[n-i-1], dp[arr[i]-1]); res = (res + p2[n - i - 1] * dp[arr[i]-1]) % mod; } printf("%lld\n", res); } |