#include <bits/stdc++.h> #define ll long long int #define pb push_back #define st first #define nd second #define pii pair<int,int> #define mp make_pair #define pll pair<long long,long long> using namespace std; const int nax = 5005; int a[nax]; int n; int dp[nax][nax * 2]; const int mod = 1e9 + 7; int ez = 0; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a + 1,a + 1 + n); if(a[1] != 1) { cout<<0<<"\n"; return 0; } dp[1][1] = 1; dp[1][0] = 1; for(int i=1;i<n;i++) { ez *= 2; ez %= mod; for(int j=0;j<nax * 2;j++) { int nxt = a[i + 1]; dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= mod; if(nxt > j + 1) continue; if(j + nxt >= 5000) { ez += dp[i][j]; ez %= mod; } else { dp[i + 1][j + nxt] += dp[i][j]; dp[i + 1][j + nxt] %= mod; } } } int ans = ez; for(int i=1;i<nax * 2;i++) { ans += dp[n][i]; ans %= mod; } cout<<ans; 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <bits/stdc++.h> #define ll long long int #define pb push_back #define st first #define nd second #define pii pair<int,int> #define mp make_pair #define pll pair<long long,long long> using namespace std; const int nax = 5005; int a[nax]; int n; int dp[nax][nax * 2]; const int mod = 1e9 + 7; int ez = 0; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a + 1,a + 1 + n); if(a[1] != 1) { cout<<0<<"\n"; return 0; } dp[1][1] = 1; dp[1][0] = 1; for(int i=1;i<n;i++) { ez *= 2; ez %= mod; for(int j=0;j<nax * 2;j++) { int nxt = a[i + 1]; dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= mod; if(nxt > j + 1) continue; if(j + nxt >= 5000) { ez += dp[i][j]; ez %= mod; } else { dp[i + 1][j + nxt] += dp[i][j]; dp[i + 1][j + nxt] %= mod; } } } int ans = ez; for(int i=1;i<nax * 2;i++) { ans += dp[n][i]; ans %= mod; } cout<<ans; return 0; } |