A - Dodecagon

• Quiz
  • https://atcoder.jp/contests/agc051/tasks/agc051_a
• AC
  • https://atcoder.jp/contests/agc051/submissions/19089349
• 解説
  • 野生の解説が見当たらなかったので書いておく
  • 公式editorialは読んだものとします
• d=2の時の解は3通り
• 追記：(1,1)x6の意味：一番外側の辺のパターンが1,1,1,1,1,1,1,1,1,1,1,1ということ

• f(a,0)は1通り
  • これは（点が縮約して）正六角形になり、三角でしか埋められないので1通り
  • f(a,0) = 1
• 漸化式 f(a,b) = f(a-1,b) + f(a,b-1)
  • メモ化再帰などで実装するとO(N²)なのでTLEする
  • 小さい値で実験してOEISに投げても解ける
• 漸化式の図示
  • 下図のようになるので、f(a,b)の値はどのルートを通ってきたかの場合の数となるので二項係数となる