yukicoder : No.737 PopCount

遅れて参加したけど、なんとか全完。
https://yukicoder.me/problems/no/737

問題

popcount(x) := xを2進数表記したときの各桁の1の登場回数　とする。
正整数Nが与えられる。
を求めよ。

解法

自分は桁DPで解いた。

num(i,j,k) := 上からi桁目まで見たとき、1のbitがj個あり、かつkが上位i桁がNと一致するかどうかの真偽値と一致するときの組み合わせ数
dp(i,j,k) := 同上のときの組み合わせ数ではなく、上からi桁目まで見た値の総和

上の桁から順に0,1のビットを当てはめていく場合を考え、num,dpを順に埋めていく。
以下のコードでは整数をleading zero含め60桁の２進数とみなし、最終的にdp(60,x,k)*xの総和を取っている。

ll A;
ll dp[62][62][2];
ll num[62][62][2];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A;
	num[0][0][1]=1;
	FOR(i,60) {
		FOR(j,61) {
			ll m=(1LL<<(59-i));
			
			(dp[i+1][j][0] += dp[i][j][0])%=mo;
			(num[i+1][j][0] += num[i][j][0])%=mo;
			
			(dp[i+1][j+1][0] += dp[i][j][0]+m%mo*num[i][j][0])%=mo;
			(num[i+1][j+1][0] += num[i][j][0])%=mo;
			
			if(A&m) {
				(dp[i+1][j][0] += dp[i][j][1])%=mo;
				(num[i+1][j][0] += num[i][j][1])%=mo;
				
				(dp[i+1][j+1][1] += dp[i][j][1]+m%mo*num[i][j][1])%=mo;
				(num[i+1][j+1][1] += num[i][j][1])%=mo;
			}
			else {
				(dp[i+1][j][1] += dp[i][j][1])%=mo;
				(num[i+1][j][1] += num[i][j][1])%=mo;
			}
		}
	}
	
	ll ret=0;
	FOR(i,61) ret+=(dp[60][i][0]+dp[60][i][1])*i;
	cout<<ret%mo<<endl;
}

まとめ

シンプルな問題設定でいいね。