AGC017 A - Biscuits
A - Biscuits
思考過程も含めて、自分の解法を書きます。
あまり証明などはしません。きちんとした解説が読みたい方は、公式や他の記事を読んでください。
解法
まず途中で使うことを書きます。
これは二項係数の和です。二項係数のwikiにもDEGwerさんの数え上げpdfにも載っています。
また、
これは二項係数の奇数項のみからなる和と、偶数項のみからなる和です。どちらもに一致します。
競プロをしていて二項係数でなんやかんやするときは、上も下も使いますよね。
では、問題に戻ります。
ビスケットの個数は、偶奇だけが気になるので入力を受け取るときに全て%2します。
目的は、いくつかビスケットの個数を選び、その和を2で割った余りをPにする選び方を数え上げることです。
言い換えると、Pが0ならば和を偶数にする選び方、Pが1ならば和を奇数にする選び方の数え上げがしたいです。
まず P = 0 のときを考えます。
いくつか選んで和を偶数にしたければ、0をいくつか選ぶことと、1を偶数個選ぶことをすればいいです。
それぞれを考えて、あとで積を取ることにします。
先に、0の選び方を数えます。0の個数をc[0]としたとき、0を0個以上c[0]個以下選ぶ方法は通りあります。
二項係数の和と考えても、0のそれぞれを選ぶ選ばないで2通りずつあるから2のc[0]乗であると考えても、どちらでもいいです。
次に1を偶数個選ぶ選び方を数えます。1の個数をc[1]としたときに、その選び方は通りあります。
まさに上に書いた、二項係数の偶数項のみからなる和です。
ただし、1の個数が0個のときはこの選び方は0と数えることにします。
1の個数が0個であるときは、0をいくつか選ぶ場合の数が答えです。
1の個数が0個でないときは、0をいくつか選ぶ場合の数と1を偶数個選ぶ場合の数の積が答えです。
P = 1 のときもほとんど同じです。1の個数が0であってもなくても、
0をいくつか選ぶ場合の数と1を偶数個選ぶ場合の数の積が答えです。
整理すると、1の個数が0個であるときは、P = 0 なら、通り。P = 1 なら、0通り。
1の個数が0でないときは、通り。
ここまで考えると、公式の解説pdfと同じことをしています。
