きままにものづくり

日々の気付いたことなんかを書いてます。

SRM578Div1

結果:0 pt
Easyのモジュラ逆数の計算でバグを埋め込んでしまった。
バグ取りをしていたら、時間がなくなってしまった。

GooseInZooDivOne

はじめ、モジュラ逆数を求めるのに拡張ユークリッドの互除法を用いた。
これ自体にはバグを埋め込まなかったが、時間がかかってしまった。
計算時間には余裕があったので、オイラーの定理を利用した方法に実装しなおした。
バグの原因は、組み合わせの和を求めるときに閉区間にすべきところを開区間にしていたことが原因。
モジュラ逆数が入ってしまうと、結果からバグの位置を特定するのが難しい。

解答の方ではモジュラ逆数を用いずに、以下の式を用いている。
 _n C _0 + _n C _2 + ... + _n C _{n-1} = 2^{n-1}

上の式の証明を簡単にする。
あまり、厳密ではない。
二項定理の式
 (a+b)^n = {}_n C _0 \times a^0 \times b^n  + _n C _1 \times a^1 \times b^{n-1} + ... + _n C _n \times a^n \times b^0
a=b=1の時を考える。
2^n =  {}_n C _0 + _n C _1 + ... + _n C _n = \sum_{r=0}^n {}_n C _r
rが偶数の時と、奇数の時とに分ける。
 \sum^n_{r=0} {}_nC_r = \sum_{r=0}^{\frac{n-1}{2}} {}_nC_{2r} + \sum_{r=0}^{\frac{n-1}{2}} {}_nC_{2r+1}
ここで、
_n C _r = _n C _n-r
なので、
 \sum^{\frac{n-1}{2}}_{r=0} {}_n C _{2r} = \sum^{\frac{n-1}{2}} _{r=0}{}_n C _{2r+1}
となる。
よって、
 2^n=2\times \sum_{r=0}^{\frac{n-1}{2}} {}_n C _{2r}
両辺を2で割ると、
 2^{n-1}=\sum^{\frac{n-1}{2}}_{r=0} {}_nC_{2r}