No.737 PopCount

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 100
作問者 :

ei1333333 / テスター :

beet

8 ProblemId : 2075 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2018-09-28 01:10:29

問題文

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

$V (x) = x \times p o p c o u n t (x)$

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

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

入力

$N$

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

出力

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

サンプル

サンプル1

入力

出力

$p o p c o u n t (1) = 1, p o p c o u n t (2) = 1, p o p c o u n t (3) = 2, p o p c o u n t (4) = 1, p o p c o u n t (5) = 2$ です。

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

サンプル2

入力

出力

サンプル3

入力

23072602871

出力

123456789

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

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