ABC 214G : Three Permutations
問題文:https://atcoder.jp/contests/abc214/tasks/abc214_g
問題概要
日本語なので略。
公式解説を読んでて分からなかったところだったり、自分が類題を解くときにつまづきそうなところだったりをメモがてら書きます。
Vandermondeの畳み込みと一般化二項係数
以前 2nCnの公式 - Lilliput Steps という記事を書いたのですが、ここで示した等式は Vandermonde の畳み込みという名前が付いていました。
実は、二項係数を以下のように拡張した枠組み
を考えると、Vandermondeの畳み込みを出発点として様々な畳込み公式を導くことができます。
ここでは、上記の二項係数を一般化二項係数と呼ぶことにします。