yukicoder No.589 Counting Even

nを2進法で表したときの1の個数をpopcnt(n)とおく
結論からいうとN+1-2^popcnt(N)が答え
方針はいろいろあるがいずれの場合も奇数が2^popcnt(N)個あることを示す

・パスカルの三角形
（以下、「n段目の左からm番目」という表現で、 $_{n}C_{m}$ に対応するマスを指すものとする）
パスカルの三角形偶奇 - Google 検索

       1        ←0段目
      1 1       ←1段目
     1 0 1      ←2段目
    1 1 1 1     ←3段目
   1 0 0 0 1    ←4段目
  1 1 0 0 1 1   ←5段目
 1 0 1 0 1 0 1  ←6段目
1 1 1 1 1 1 1 1 ←7段目

パスカルの三角形を睨むと、規則的な構造をしていることが分かる。
具体的には「(2^k)段目以降は、それより前の段の繰り返しである」（★）（証明は後述）
このことから、求めるべき答えは ans[n]=2*ans[n-2^k] という再帰式で求まる（ただし2^kはn以下の最大2冪）
この漸化式は「nの最上位bitを消して値を2倍する」というものなので、ans[0]=1とあわせて、結局ans[n]=2^popcnt(n)になることが分かる
★の証明の概略
(1)ある段が全て奇数なら、その直下の段は、両端の1を除いて全て偶数である
(2)左からnマス目の数は、k段下では左からn～(n+k)マス目までのk+1マスにのみ影響する
(3)(1)(2)から帰納的に(2^k-1)段目は全て奇数であることがわかり、主張が示せる

・lucasの定理
主張と証明は下記ページに丸投げ
Lucasの定理とその証明 | 高校数学の美しい物語
以下、ni,miという記号は上記サイトにならう。
定理より
nCmが奇数
⇔「mi=1⇒ni=1」
⇔「mの2進法表記で1である位」は「nの2進法表記で1である位」に含まれる
よって明らかにそのようなmは2^popcnt(n)個

・legendreの定理
自分が実際に解いた方針はこれ
主張と証明は下記ページに丸投げ
ルジャンドルの定理（階乗が持つ素因数のべき数） | 高校数学の美しい物語
先ほど同様にni,miの記号を定める。
k!が2で割れる回数をf(k)とおく。
$_{n}C_{m}=\dfrac{n!}{m!(n-m)!}$ が奇数
⇔f(n)=f(m)+f(m')　（m'=n-mとおいた）
ここで一般に整数a,bについて $\lfloor\dfrac{a+b}{2}\rfloor\geq\lfloor\dfrac{a}{2}\rfloor+\lfloor\dfrac{b}{2}\rfloor$ であり、等号成立は「a,bの少なくとも一方が偶数」が必要十分
よってこのことから
f(n)=f(m)+f(m')
⇔ $\forall i.\lfloor\dfrac{n}{2^i}\rfloor=\lfloor\dfrac{m}{2^i}\rfloor+\lfloor\dfrac{m'}{2^i}\rfloor$
⇔∀i.miとm'iの少なくとも一方は0
ここでn=m+m'であったことから、（足し算の際に繰り上がりが起こらないので）「mの2進法表記で1である位」は「nの2進法表記で1である位」に含まれることが分かる
そのようなmは2^popcnt(n)個

（直感的には、「nが2^kの箱に最適に入っている状態を想像する（例えば13なら8,4,1の箱）。nをmとm'に分けたとき、もし大きさ2^iの箱を分解することがあれば、2^iで割った時の値が1小さくなってしまうので困る。つまり、各箱についてmとm'のどちらが取るかを決めるしかない。よって2^popcnt(n)」という感じ）

実装はpopcount関数を使うだけ

main(long n){scanf("%ld",&n);printf("%ld",n+1-(1LL<<__builtin_popcountll(n)));}

79B

メモ

yukicoderでゆるふわgolf

yukicoder No.589 Counting Even