AGC017 A

https://atcoder.jp/contests/agc017/tasks/agc017_a

考えたこと

最終的に食べたビスケットの総数の余りが0であろうが1であろうが偶数個の入ったビスケットは結果に影響しない。
ビスケットが偶数個入った袋のみを何個選ぼうが総計が偶数個にしかならない。
ビスケットが奇数個入った袋を偶数個選ぶと、余りが0になり、奇数個選ぶと余りが1になる。

考察パート

コーナーケース(ビスケットが奇数個入った袋が0)
これは $p= 1$ のときは答えが0になる。 $p= 0$ のときは $2^ n$ となる。

ビスケットが偶数個入った袋をa個、ビスケットが奇数個入った袋をb個とする。
今の段階で以下の式が成り立つ。
$a+b=n$

考えたことをまとめるとpの値によらずビスケットが偶数個入った袋はいくつ選んでも良い。pの値により場合分けが必要になるのはビスケットが奇数個入った袋。

ビスケットが奇数個入った袋から奇数袋分選ぶことは以下の式で表すことが出来る。
$_b C_1 + _b C_3 + _b C_5 + _b C_7 + _b C_9 + _b C_{11} + ....+$
ビスケットが奇数個入った袋から偶数袋分選ぶことは以下の式で表すことが出来る。
$_b C_0 + _b C_2 + _b C_4 + _b C_6 + _b C_8 + _b C_{10} + ....+$

よってそれぞれの場合について解答は以下の計算式で求められる。 $2 ^ a \times( _b C_1 + _b C_3 + _b C_5 + _b C_7 + _b C_9 + _b C_{11} + ....+ )$

$2 ^ a \times( _b C_0 + _b C_2 + _b C_4 + _b C_6 + _b C_8 + _b C_{10} + ....+ )$

コーナーケース以外でなぜ解答が $2 ^ {n-1}$ となるのか

二項定理より以下の式が成り立つ。
$_n C_0 + _n C_1x + _n C_2x ^2 +.... + _n C_nx ^ n = (1+x) ^ n$ ……①

①に $x=1$ を代入すると以下の式が得られる
$_n C_0 + _n C_1 + _n C_2 +.... + _n C_n = 2 ^ n$ ……②

また①に $x=-1$ を代入すると以下の式が得られる
$_n C_0 - _n C_1 + _n C_2 - _n C_3 + ....+ (-1) ^ n _n C_n = 0$
変形すると以下のようになる。
$_n C_0 + _n C_2 + _n C_4 + .... = _n C_1 + _n C_3 + _n C_5 + ....$

この式の左辺を $A$ 右辺を $B$ とする。両辺にAを足すと以下のようになる。
$A + B = B + B$
①より $A + B = 2 ^ n$ なので $B = 2 ^ {n-1}$
同様にして両辺にAを足した場合、 $A = 2 ^ {n-1}$ が得られ、以下のようになる。
$_n C_0 + _n C_2 + _n C_4 + .... = _n C_1 + _n C_3 + _n C_5 + .... = 2 ^ {n-1}$