fork download
copy 
  1. // #pragma GCC optimize("Ofast,unroll-loops")
  2. #include <climits>
  3. #include <unordered_map>
  4. #include <random>
  5. #include <chrono>
  6. #include <numeric>
  7. #include <iostream>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <map>
  11. #include <queue>
  12. #include <deque>
  13. #include <stack>
  14. #include <functional>
  15. #include <bitset>
  16. #include <string>
  17. #include <sstream>
  18. #include <fstream>
  19. #include <iomanip>
  20. #include <cmath>
  21. #include <cassert>
  22. #include <list>
  23. #include <forward_list>
  24. #include <set>
  25. #include <unordered_set>
  26. #include <cstdint>
  27. #include <utility>
  28. // #pragma GCC target("avx2,fma")
  29.  
  30. using namespace std;
  31.  
  32. using ll = long long;
  33. using ld = long double;
  34. using ull = unsigned long long;
  35.  
  36. #define all(x) begin(x), end(x)
  37. #define X first
  38. #define Y second
  39. #define isz(x) ((int)size(x))
  40.  
  41. const int MOD = 1e9 + 7;
  42.  
  43. class int_mod {
  44. 	ll value;
  45.  
  46.  public:
  47. 	int_mod() : value(0) {}
  48.  
  49. 	int_mod(ll a) {
  50. 		if (a >= MOD) a %= MOD;
  51. 		value = a;
  52. 	}
  53.  
  54. 	int_mod operator+(int_mod other) {
  55. 		ll res = this->value + other.value;
  56. 		if (res >= MOD) res -= MOD;
  57. 		return res;
  58. 	}
  59.  
  60. 	int_mod operator-(int_mod other) {
  61. 		ll res = this->value - other.value;
  62. 		if (res < 0) res += MOD;
  63. 		return res;
  64. 	}
  65.  
  66. 	int_mod operator*(int_mod other) {
  67. 		long long res = 1LL * this->value * other.value;
  68. 		if (res >= MOD) {
  69. 			res %= MOD;
  70. 		}
  71. 		return res;
  72. 	}
  73.  
  74. 	int_mod operator+(ll other) { return *this + int_mod(other); }
  75.  
  76. 	int_mod operator-(ll other) { return *this - int_mod(other); }
  77.  
  78. 	int_mod operator*(ll other) { return *this * int_mod(other); }
  79.  
  80. 	int_mod operator=(int_mod other) { return value = other.value; }
  81.  
  82. 	int_mod operator=(ll other) { return *this = int_mod(other); }
  83.  
  84. 	int_mod operator+=(int_mod other) { return *this = *this + other; }
  85.  
  86. 	int_mod operator-=(int_mod other) { return *this = *this - other; }
  87.  
  88. 	int_mod operator*=(int_mod other) { return *this = *this * other; }
  89.  
  90. 	explicit operator ll() { return value; }
  91. };
  92.  
  93. std::istream& operator>>(std::istream& is, int_mod &imod) {
  94. 	ll x;
  95.     is >> x;
  96.     imod = x;
  97.     return is;
  98. }
  99.  
  100. std::ostream& operator<<(std::ostream& os, int_mod imod) {
  101. 	return os << (ll)imod;
  102. }
  103.  
  104. const int MAXN = 3010;
  105. const int MAXSUM = 10010;
  106.  
  107. int_mod binpow(int_mod a, int b) {
  108.   if (!b) return 1;
  109.   if (b & 1) return binpow(a, b - 1) * a;
  110.   auto x = binpow(a, b / 2);
  111.   return x * x;
  112. }
  113.  
  114. const int_mod INV2 = binpow(2, MOD - 2);
  115.  
  116. int_mod dp[MAXN][MAXSUM];
  117. int a[MAXN];
  118.  
  119. void solve() {
  120.   int n;
  121.   cin >> n;
  122.   for (int i = 0; i < n; ++i) cin >> a[i];
  123.   int sum;
  124.   cin >> sum;
  125.   for_each(all(dp), [](int_mod v[]) {
  126.     fill(v, v + MAXSUM, 0);
  127.   });
  128.   dp[0][0] = binpow(2, n);
  129.   for (int i = 0; i < n; ++i) {
  130.     for (int j = 0; j <= sum; ++j) {
  131.       dp[i + 1][j] = dp[i][j];
  132.       if (j - a[i] >= 0) dp[i + 1][j] += dp[i][j - a[i]] * INV2;
  133.     }
  134.   }
  135.   cout << dp[n][sum] << '\n';
  136. }
  137.  
  138. signed main() {
  139.   cin.tie(0)->sync_with_stdio(0);
  140.   #ifdef LOCAL
  141.     freopen("in.txt", "r", stdin);
  142.     freopen("out.txt", "w", stdout);
  143.   #endif
  144.   int t = 1;
  145.   // cin >> t;
  146.   while (t --> 0) solve();
  147.   return 0;
  148. }
Success #stdin #stdout 0.08s 239016KB
comments (?)
stdin
copy 
5
1 1 1 1 1
4
stdout
copy 
10
https://ideone.com/YrdD28
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!