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