gistfile1.cpp

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#include <stdarg.h>
#include <string>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>

using namespace std;

/* DEBUG */
#define D(x) cerr<<__LINE__<<" "#x" "<<x<<endl
#define D_v(x) for(int i=0;i<x.size();cerr<<x[i++]<<" ")

#define ALL(x) x.begin(),x.end()
#define ARRSIZE(x) (sizeof(x)/sizeof(x[0]))

template<typename T> void print( T a ) {
  cerr << a;
}
static void print( long long a ) {
  cerr << a << "L";
}
static void print( string a ) {
  cerr << '"' << a << '"';
}
template<typename T> void print( vector<T> a ) {
  cerr << "{";
  for ( int i = 0 ; i != a.size() ; i++ ) {
    if ( i != 0 ) cerr << ", ";
    print( a[i] );
  }
  cerr << "}" << endl;
}
template<typename T> void eq( int n, T have, T need ) {
  if ( have == need ) {
    cerr << "Case " << n << " passed." << endl;
  } else {
    cerr << "Case " << n << " failed: expected ";
    print( need );
    cerr << " received ";
    print( have );
    cerr << "." << endl;
  }
}
template<typename T> void eq( int n, vector<T> have, vector<T> need ) {
  if( have.size() != need.size() ) {
    cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements.";
    print( have );
    print( need );
    return;
  }
  for( int i= 0; i < have.size(); i++ ) {
    if( have[i] != need[i] ) {
      cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << ".";
      print( have );
      print( need );
      return;
    }
  }
  cerr << "Case " << n << " passed." << endl;
}
static void eq( int n, string have, string need ) {
  if ( have == need ) {
    cerr << "Case " << n << " passed." << endl;
  } else {
    cerr << "Case " << n << " failed: expected ";
    print( need );
    cerr << " received ";
    print( have );
    cerr << "." << endl;
  }
}
// END CUT HERE


const int MAXN = 35, MAXS = 30005;
long long a[MAXN][MAXS];
long long b[MAXN][MAXS];

long long Choose[MAXN][MAXN];
long long choose(long long n, long long k){
  if (k < 0 or k > n) return 0;
  if (Choose[n][k] != -1) return Choose[n][k];
  if (k == 0 or n == k) return 1;
  return Choose[n][k] = choose(n-1, k) + choose(n-1, k-1);
}

class Jewelry {
public:
  long long howMany(vector <int> v) {
    memset(Choose, -1, sizeof Choose);
    long long ans = 0;
    sort(v.begin(), v.end());
    int n = v.size();

    fill(a[0], a[0] + MAXS, 0);
    a[0][0] = 1;
    for (int i = 1; i <= n; ++i){
      for (int k = 0; k < MAXS; ++k){
        a[i][k] = a[i-1][k];
        if (k - v[i-1] >= 0) a[i][k] += a[i-1][k - v[i-1]];
      }
    }

    fill(b[n], b[n] + MAXS, 0);
    b[n][0] = 1;
    for (int i = n - 1; i >= 0; --i){
      for (int k = 0; k < MAXS; ++k){
        b[i][k] = b[i+1][k];
        if (k - v[i] >= 0) b[i][k] += b[i+1][k - v[i]];
      }
    }

    // for (int i = 0; i <= n; ++i){
    //   for (int k = 0; k <= 20; ++k){
    //  printf("a[%d][%d] = %lld\n", i, k, a[i][k]);
    //   }
    // }
    // for (int i = 0; i <= n; ++i){
    //   for (int k = 0; k <= 20; ++k){
    //  printf("b[%d][%d] = %lld\n", i, k, b[i][k]);
    //   }
    // }

    // for (int i = 0; i < 31; ++i){
    //   for (int j = 0; j < 31; ++j){
    //  printf("Choose(%d, %d) = %lld\n", i, j, choose(i, j));
    //   }
    // }

    ans = 0;
    for (int i = 0; i < n; ++i){
      int j = i;
      while (j < n and v[i] == v[j]) j++;
      int s = j - i;
      for (int p = 1; p <= s; ++p){
        for (int k = p * v[i]; k < MAXS; ++k){
          ans += choose(s, p) * a[i][k - p*v[i]] * b[i+p][k];

        }
      }
      i = j - 1;
    }

    return ans;
  }
};