読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

yukicoder No420 mod2漸化式

考察

・まずは素直に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)になる。

n2^{31}-1までなので、x31までしかないことが分かる。

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)