問題一覧 > 通常問題

No.737 PopCount

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 99
作問者 : ei1333333ei1333333 / テスター : beetbeet
7 ProblemId : 2075 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-09-28 01:10:29

問題文

$1$ が大好きな M さんは, ある自然数 $x$ の美しさ $V(x)$ を次のように定義しました。

  • $V(x) = x \times popcount(x)$

ここで $popcount(x)$ は $x$ を $2$ 進表記したときに現れる $1$ の数と定義します。例えば $popcount(23) = 4$ です。$23$ を $2$ 進表記すると $10111$ で, これに現れる $1$ の数は $4$ 個です。

自然数 $N$ が与えられるので $\displaystyle \sum_{i=1}^{N} V(i)$ を $10^9+7$ で割った余りで求めてください。

入力

$N$

$1$ 行に自然数 $N(1 \le N \le 10^{18})$ が与えられます。

出力

$1$ 行に答えを出力してください。

サンプル

サンプル1
入力
5
出力
23

$popcount(1) = 1, popcount(2) = 1, popcount(3) = 2, popcount(4) = 1, popcount(5)=2$ です。

$(1 \times 1) + (2 \times 1) + (3 \times 2) + (4 \times 1) + (5 \times 2) = 23$ より $23$ が答えとなります。

サンプル2
入力
30
出力
1333
サンプル3
入力
23072602871
出力
123456789

入力の $N$ が 32bit整数型に収まらない場合があることや, $10^9+7$ で割った余りで出力することに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。