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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n, m, i, j, k;
	const int mod = 1000000007;
	scanf("%d", &n);
	vector<int> a(n);
	for (i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	sort(a.begin(), a.end());
	
	// dynamik, dokladamy kolejne w kolejnosci rosnacych wag; para (pdz, wszystkie_pdz) to czesciowy wynik
	vector<long long> pdz(5001, 0); // pdz[j] = liczba szukanych podzbiorow o sumie j
	long long wszystkie_pdz = 0; // liczba wszystkich podzbiorow 
	for (i = 0; i < n; ++i) {
		for (j = 5000 - a[i]; j >= a[i] - 1; --j)
			pdz[j + a[i]] = (pdz[j + a[i]] + pdz[j]) % mod;
		long long pdz_mniejsze = 0;
		for (j = 0; j < a[i] - 1; ++j)
			pdz_mniejsze = (pdz_mniejsze + pdz[j]) % mod;
		wszystkie_pdz = (wszystkie_pdz + wszystkie_pdz - pdz_mniejsze + mod) % mod;
		if (a[i] == 1) {
			pdz[1] = (pdz[1] + 1) % mod;
			wszystkie_pdz = (wszystkie_pdz + 1) % mod;
		}
	}
	printf("%lld", wszystkie_pdz);
	return 0;
}