yukicoder No.420 mod2漸化式

最近はyukicoderの低難易度埋めてます.
その中でもおもしろいと思ったものを書き留めます.

問題

No.420 mod2漸化式 - yukicoder

解法

まず漸化式
f(0) = 1
f(n) = f(\frac{n}{2}) + (n \space mod \space 2)
がそもそも何を表しているか考えます.
ためしにいろいろ入れてみると,
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 1
f(5) = 2
f(6) = 2
f(7) = 3
f(8) = 1 ...
となります. 2のべきが1となっているところや, 数字の増え方をみると, この漸化式は（というより関数としてみると）あるnを2進数表現したときの立つ1の数, または各桁の和であると推測することができます. その観点を持って漸化式を見ると, たしかにそれらしいことがわかります.
問題に戻ります. 問題では, あるxが与えられ,

  1. f(n) = xとなるようなnの数
  2. それを満たすnの和

の2つを求める必要があります. 上の考察より, 前者は31ビット分の中に1をx個立てる場合の数を求めればよいです. これは, _{31}C_x で求まります.
後者は少し考察が必要です. 上で求めた_{31}C_xの中で, k番目のビットに1が立つ場合の数はいくらか？を考えます. この数は, kビット目に1を立てておいて他の場所にx-1個1を立てたときの場合の数に対応するので, _{30}C_{x-1}に対応します.
よって, kビット目に1が立つものは _{30}C_{x-1}個あり, このkを1から30について計算するので,
Ans = \sum_{k=0}^{30} 2^k_{30}C_{x-1}
となります. コンビネーションの部分は外に出せ,
Ans = _{30}C_{x-1} \sum_{k=0}^{30} 2^k
となり, さらに簡略化すると,
Ans = _{30}C_{x-1}(2^{31} - 1)
となり, これが和の方の答えです.
しかし, xが0のときだけ場合分けが必要なので注意です.

提出

#282657 No.420 mod2漸化式 - yukicoder

感想

漸化式の意味を理解すると大きく計算量を減らすことができる面白い問題だと思いました.