HandsShaking メモ化再帰版 srm 363 div2 mid

program topcoder
  • だいぶDPとメモ化再帰を行き来出来るようになった。
  • ただ、下のコードは桁あふれでシステムテストが通らない。
    • 桁あふれぢゃないのかな。だけど、手元では合ってるんだよな。
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class HandsShaking{
public:
  vector<long long> ans;

  long long rec(int n){
    if(ans[n] > 0) return ans[n];
    long long ret = 0;
    for(int i = 1; i < n; i += 2){
      ret += rec(i - 1) * rec(n - 1 - i);
    }
    return ans[n] = ret;
  }

  long long countPerfect(int n){
    ans.resize(n);
    fill(ans.begin(), ans.end(), 0);
    ans[0] = 1;
    return rec(n);
  }


};