fork download
copy 
  1. #include <bits/stdc++.h>
  2. #ifdef LOCAL
  3. #include "Debug.h"
  4. #else
  5. #define debug(...) 42
  6. #endif
  7. using namespace std;
  8.  
  9. template<int MOD_> struct modnum {
  10.   static constexpr int MOD = MOD_;
  11.   static_assert(MOD_ > 0, "MOD must be positive");
  12.  
  13. private:
  14.   using ll = long long;
  15.  
  16.   int v;
  17.  
  18.   static int minv(int a, int m) {
  19.     a %= m;
  20.     assert(a);
  21.     return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  22.   }
  23.  
  24. public:
  25.  
  26.   modnum() : v(0) {}
  27.   modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  28.   explicit operator int() const { return v; }
  29.   friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  30.   friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
  31.  
  32.   friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  33.   friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  34.  
  35.   modnum inv() const {
  36.     modnum res;
  37.     res.v = minv(v, MOD);
  38.     return res;
  39.   }
  40.   friend modnum inv(const modnum& m) { return m.inv(); }
  41.   modnum neg() const {
  42.     modnum res;
  43.     res.v = v ? MOD-v : 0;
  44.     return res;
  45.   }
  46.   friend modnum neg(const modnum& m) { return m.neg(); }
  47.  
  48.   modnum operator- () const {
  49.     return neg();
  50.   }
  51.   modnum operator+ () const {
  52.     return modnum(*this);
  53.   }
  54.  
  55.   modnum& operator ++ () {
  56.     v ++;
  57.     if (v == MOD) v = 0;
  58.     return *this;
  59.   }
  60.   modnum& operator -- () {
  61.     if (v == 0) v = MOD;
  62.     v --;
  63.     return *this;
  64.   }
  65.   modnum& operator += (const modnum& o) {
  66.     v += o.v;
  67.     if (v >= MOD) v -= MOD;
  68.     return *this;
  69.   }
  70.   modnum& operator -= (const modnum& o) {
  71.     v -= o.v;
  72.     if (v < 0) v += MOD;
  73.     return *this;
  74.   }
  75.   modnum& operator *= (const modnum& o) {
  76.     v = int(ll(v) * ll(o.v) % MOD);
  77.     return *this;
  78.   }
  79.   modnum& operator /= (const modnum& o) {
  80.     return *this *= o.inv();
  81.   }
  82.  
  83.   friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  84.   friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  85.   friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  86.   friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  87.   friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  88.   friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
  89. };
  90.  
  91. template<typename T> T pow(T a, long long b) {
  92.   assert(b >= 0);
  93.   T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
  94. }
  95.  
  96. template<int M> string to_string(modnum<M> x) {
  97.   return to_string(int(x));
  98. }
  99.  
  100. using num = modnum<int(1e9) + 7>;
  101. const int Z = 1000;
  102.  
  103. int main()
  104. {
  105.   ios_base::sync_with_stdio(0);
  106.   cin.tie(0);
  107.   int n;
  108.   while (cin >> n)
  109.   {
  110.     vector<int> a(n + 1);
  111.     for (int i = 1; i <= n; i++)
  112.       cin >> a[i];
  113.  
  114.     vector<vector<num>> f(n + 1, vector<num>(Z * 2 + 1));
  115.     f[0][0 + Z] = 1;
  116.     for (int i = 0; i < n; i++)
  117.     {
  118.       set<int> values;
  119.       for (int ii = i + 1; ii <= n; ii++)
  120.       {
  121.         for (int j = -Z; j <= Z; j++)
  122.         {
  123.           int jj = j + a[ii];
  124.           if (j != 0 && -Z <= jj && jj <= Z)
  125.             f[ii][jj + Z] += f[i][j + Z];
  126.         }
  127.  
  128.         for (int v : values)
  129.         {
  130.           int jj = v + a[ii];
  131.           f[ii][jj + Z] += f[i][0 + Z];
  132.         }
  133.  
  134.         if (a[ii])
  135.           values.insert(a[ii]);
  136.       }
  137.     }
  138.  
  139.     num ans;
  140.     for (int i = 0; i <= n; i++)
  141.       for (auto u : f[i])
  142.         ans += u;
  143.  
  144.     cout << ans << '\n';
  145.   }
  146. }
  147.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hc6QMH
language:
C++14 (gcc 8.3)
created:
11 hours 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!