#include <cstdio> #include <algorithm> using namespace std; int N; int A[5000]; unsigned T[5000 * 5000 + 1]; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &A[i]); sort(A, A + N); T[0] = 1; int nzix = 0; for (int i = 0; i < N; i++) { int x = A[i]; //for (int y = 5000 * 5000 - x; y >= x-1; y--) { if (nzix >= x-1) { for (int y = nzix; y >= x-1; y--) { T[x + y] += T[y]; //T[x + y] %= 1'000'000'007U; if (T[x + y] > 1'000'000'007U) T[x+y] -= 1'000'000'007U; } nzix += x; } } unsigned result = 0; for (int i = 1; i <= 5000 * 5000; i++) { result += T[i]; //T[i] %= 1'000'000'007U; if (result >= 1'000'000'007U) result -= 1'000'000'007U; } printf("%u\n", result); 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 | #include <cstdio> #include <algorithm> using namespace std; int N; int A[5000]; unsigned T[5000 * 5000 + 1]; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &A[i]); sort(A, A + N); T[0] = 1; int nzix = 0; for (int i = 0; i < N; i++) { int x = A[i]; //for (int y = 5000 * 5000 - x; y >= x-1; y--) { if (nzix >= x-1) { for (int y = nzix; y >= x-1; y--) { T[x + y] += T[y]; //T[x + y] %= 1'000'000'007U; if (T[x + y] > 1'000'000'007U) T[x+y] -= 1'000'000'007U; } nzix += x; } } unsigned result = 0; for (int i = 1; i <= 5000 * 5000; i++) { result += T[i]; //T[i] %= 1'000'000'007U; if (result >= 1'000'000'007U) result -= 1'000'000'007U; } printf("%u\n", result); return 0; } |