Combinationが肝となる問題って数学ゲーとか言われて結構難しくないですかってことでいろいろ考察してみました。
(a+b)Caはa+b人いる中でa人を選び、b人を除外するときの場合の数です。
これは経路数にも言い換えられて、タテaマスヨコbマスのgridで左下から右上に行く際の場合の数とも見ることができます。
さらに経路数といえば禁止領域ですね。途中でy-x>=kとはなっては行けない時の場合の数も簡単に求まります。カタラン数とかこれで求められます。
以上をまとめると、Combinationは2値a,bについての演算で、a+b、a-bの条件が付いている時のみ使用可能ということです。
ここで言いたいことはCombinationは相当単純なシチュエーションじゃないと出てこないということです。なぜなら２値の和と差のみが条件になる数え上げにしか使えないからです。
つまり問題を解いていてこれはCombinationを使う問題だなと思ったら特定の2つの値に注目すればいいということになります。
https://beta.atcoder.jp/contests/agc021/tasks/agc021_e
こういう問題とか解いてみると言っていることが解ると思います。
他にも、
https://beta.atcoder.jp/contests/agc018/tasks/agc018_e
こんな問題がありますが、これを見てわかる通り、経路数は長方形領域の和に強いです。つまり式で言えばa=constの時の和、またはb=constの時の和に強いということです。パスカルの三角形上で見ても同じことが言えます。
でもCombinationのΣとか入る複雑な式になりそうだと思った時はとりあえず経路数で言い換えるのが汎用的な解法だと思います。
