脳log[20211101]

2021年11月01日 (月) [AtCoder] 精進。ARC023-C「タコヤ木」(青 diff)。累積和の累積和の累積和の……を求めたいのだけど、累積和の項数と累積和を重ねる回数の、どちらかが N(≦2000)でどちらかが A(≦10^9)で制約されるので、手続き的に答えを求めることができない。とりあえず 10×10 の表を作って眺めてみて、Wikipedia で「パスカルの三角形」を検索した。そうしたらコンビネーションで求められることがわかった。提出 #26976714 (AC / 427 Byte / 64 ms)。同じページに「カタラン数」の文字も見えた。これは ABC の関連ツイートで見かけたことがある(が知らない)。■検索してブログを読むと、仕切りを加えた組み合わせを考えることで累積和やらパスカルの三角形やらを経由せず直接コンビネーションを答えに導けるようだった。それは高校で習ったし AtCoder の問題でも利用したことがある。知っているが引き出せなかった。むむむ。