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]; } };