yukicoder No420 mod2漸化式 - tookunn’s diary

問題

考察

・まずは素直に $f(n)$ を書き連ねてみる。
$f(0) = 0$
$f(1) = f(0) + 1 = 1$
$f(2) = f(1) + 0 = 1$
$f(3) = f(1) + 1 = 2$
$f(4) = f(2) + 0 = 1$
$f(5) = f(2) + 1 = 2$
$f(6) = f(3) + 0 = 2$
$f(7) = f(3) + 1 = 3$
$f(8) = f(4) + 0 = 1$
$f(9) = f(4) + 1 = 2$
$f(10) = f(5) + 0 = 2$
$f(11) = f(5) + 1 = 3$

・ $n$ が奇数の時に $f(n/2) + 1$ になっていることに着目する。

・つまり, $n$ を2進数で表現した時1が立っているビットの数が $f(n)$ になる。

・ $n$ は $2^{31}-1$ までなので、 $x$ は $31$ までしかないことが分かる。

・ $n$ を普通に $0$ から $2^{31}-1$ まで見て立っているビットをカウントしても計算量が多い。

・ここでは半分全列挙みたいなことをイメージする。

・ $2^{31}-1$ は31ビットなので,15ビットと16ビットに分ける。

・つまり, $0$ から $2^{16}-1$ まで, $2^{16}$ から $2^{31}-1$ 。

・あとはdp[立っているビット数]とかにカウントする。

・ $0$ から $2^{16}-1$ までの数で立っているビット数をa, $2^{16}$ から $2^{31} - 1$ までの数で立っているビット数をbとする。

・ $dp1[a] * dp2[b]$ が31ビットの内立っているビットが $a + b$ の組み合わせが計算できる。

・総和はdp[立っているビット数]とsum[立っているビット数]を利用すれば計算可能。

ソースコード

変数名にdpとありますがcntとかcountの方が良かったですね。DPではないので。

X = int(input())
if X <= 31:
	dp1 = [0 for i in range(17)]
	dp2 = [0 for i in range(16)]
	sum1 = [0 for i in range(17)]
	sum2 = [0 for i in range(16)]
	for i in range(1 << 16):
		c = 0
		for j in range(16):
			c += ((i >> j) & 1)
		sum1[c] += i
		dp1[c]+=1
	for i in range(1 << 15):
		c = 0
		for j in range(15):
			c += ((i >> j) & 1)
		sum2[c] += (i << 16)
		dp2[c]+=1
	s = 0
	t = 0
	for i in range(17):
		for j in range(16):
			if i + j == X:
				s += dp1[i] * dp2[j]
				t += (dp1[i] * sum2[j]) + dp2[j] * sum1[i]
	print(s,t)
else:
	print(0,0)