http://yukicoder.me/problems/no/520
解説
http://yukicoder.me/submissions/176154
http://yukicoder.me/problems/no/520/editorial
解説の図とソースコードを見ながら見るといいです。
まず、関数f(a,b)を定義しておく。
これは、以上のような図と対応しており、このときに線分が重ならないように線を引く引き方を返す。
f(a,b)は、
- aかbが1なら1
- f(a-1,b)+f(a,b-1)
で求められる。
解説の左図の場合は、三辺の分割点を全列挙して数え上げる。
この時、分かれている3つの三角形は関数fで組み合わせ数を数えることができて、その積がその時の組み合わせ数になる。
解説の右図の場合は、以下の図のように考えると、関数fで数え上げることができる。
これで解ける
