SRM501 Div2 Hard

1000
メモ化する。
memo[長さ][これまでの合計][最後に使った数][何連続で減少しているか];

const lli mod = 1000000007;

const int LEN = 40 + 1;
const int SUM = 40 * 40 + 1;
const int N = 40 + 1;

lli memo[LEN][SUM][N][2];

lli rec(int len, int sum, int last, int cons, const vector<int> &v)
{
  if (cons == 2) return 0;
  if (v.size() == len) return 1;

  lli &ret = memo[len][sum][last][cons];
  if (ret != -1) return ret;

  lli total = 0;

  for (int n = 0; n < N; ++n) {
    if (v[len] == -1 || v[len] == n) ; else continue;
    if (n * len <= sum) {
      total += rec(len + 1, sum + n, n, (n < last) ? cons + 1 : 0, v);
      total %= mod;
    }
  }

  return ret = total;
}

class FoxAverageSequence {
public:
  int theCount(vector <int> seq)
  {
    fill(&memo[0][0][0][0], &memo[LEN - 1][SUM - 1][N - 1][2], -1);
    return rec(0, 0, 0, 0, seq);
  }
};