SRM401 Div1Easy FIELDDiagrams

解法
カタラン数を求めるとよい。
http://mathworld.wolfram.com/CatalanNumber.html

Wikipediaの格子状の経路数え上げの項目が参考になる。Nを1増加して計算したうえで、はじめの経路分を引けばよい。

class FIELDDiagrams {
public:
  ull nCr(ull n, ull r){
    ull ret = 1;
    if(n-r<r) r = n-r;
    for(ull i=1; i<r+1 ; i++, n--)
      (ret *= n) /= i;
    return ret;
  }
  
  long long countDiagrams(int N) {
    N++;
    return nCr(2*N, N) - nCr(2*N, N-1) - 1;
  }
};