二項係数（ｎCｒ）について

高校数学ではさらっと習ったぐらいですが、まさか大人になってこんなに苦しむことになるとは思いませんでした「二項係数」
こちらをコードベース、競技プログラミングで使われている方法をまとめます。
＊こちらも自分のメモ用です。

奇数・偶数個の組み合わせ数の裏技

これは初見〇しだと思っているのですが以下のような場合

nC0 + nC2 + nC4 +...   （偶数個取り出す場合）
nC1 + nC3 + nC5 +...　（奇数個取り出す場合）

は、上式も下式も

2**(n-1)

と一発で求めることができるのです。
。。。へぇ～

さて、感覚的ですがなぜこの算出でいいのかについてちょっとした補足を。
まず、

nC0 + nC1 + nC2 + nC3 + nC4 + ... = 2**n

としたときにこれを「半分ずつ分けましょう！」とすると2**(n-1)=(1/2)*2**nとなるのはわかりますよね。
これを偶奇に二つにしたものが上記の算出になるのですが、どうですかね？めちゃくちゃな算出ですが（笑）
さすがに乱暴すぎますかね。。。

もうちょっと踏み込むと、例えば偶数個選んでいると式は以下になります。

nC0 + nC2 + nC4 +...   （偶数個取り出す場合）

まず、nC0について「ｎ個から０個選ぶ」組み合わせですが、選択する個数を一つ増やすと「ｎ個から１個選ぶ」奇数個取り出す組み合わせになるのはわかるかなと。
同様に偶数個の組み合わせ数について調べていくと、偶数個の組み合わせ数各値が、一対一で奇数個の組み合わせ数に対応しているという状況になります。
なので、全体の場合の数を半分にしたものを偶奇に当てはめて使えるといったぐあいです。
どうですかね？感覚的にもつかめたら幸いです。