C]競技プログラミングhttp://codeforces.com/contest/914/problem/Cあるxについて以下の変換を考える。xを2ビット表記したときの1の個数の総和」2進数表記された数Nが与えられる。桁DP解法http://codeforces.com/contest/914/submission/34415059まず気付くべき性質がある「2^1000以下の数はg(x)を1回通すと1000以下の数になる」よって、N以下の数について変換を1回通した形、つまり、2進数にしたときの1の数だけを考えればいいことになる。ここから、以下の桁DPを使う。