HandsShaking srm 363 div2 mid

適当な人を1番と決めて、時計回りに2, .., nと番号を振る。この時、1と3が握手しちゃうと、2が誰とも握手出来ない。同様の理由で、1が握手し得るのは2, 4, ..., n だけ。で、1とiの人が握手すると円卓がnより真に小さい部分グループに分かれる。この問題の構造を利用して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>
using namespace std;
class HandsShaking{
public:
  long long countPerfect(int n){
    vector<long long> ret(100, 0);
    ret[0] = 1;
    for(int i = 2; i <= n; i += 2){
      for(int j = 0; j < i; j += 2){
	ret[i] += ret[j] * ret[i - j - 2];
      }
    }
    return ret[n];
  }
};