DivideSum

問題の言いかえ

$1～n$ までの整数を、$2$で最大何回割り切れるかに応じて分けて考えます。
$1$以上$n$以下で、$2$で最大$k$回割り切れる整数の集合を、$s(k,n)$と定義します。

例として、 $n = 18$ の場合で考えてみましょう。
$s(0,18) = \{1,3,5,7,9,11,13,15,17\}$
$s(1,18) = \{2,6,10,14,18\}$
$s(2,18) = \{4,12\}$
$s(3,18) = \{8\}$
$s(4,18) = \{16\}$

まず、$s(0,18)$は、18未満の奇数の集合に等しいです。

$s(1,18)$の各要素について、$f$ を適用することを考えてみます。
$f(2) = f(1) = 1$
$f(6) = f(3) = 3$
$f(10) = f(5) = 5$
$f(14) = f(7) = 7$
$f(18) = f(9) = 9$
これは、最大$0$回割り切れる集合の最初の$5$項と等しくなっています。

$s(2,18)$に関しても、$f$を適用してみると…
$f(4) = f(2) = f(1) = 1$
$f(12) = f(6) = f(3) = 3$
これは、最大$0$回割り切れる集合の最初の$2$項と等しくなっています。

結局、$2$で割り切れる回数別で分けて考えた場合、$s(k,n)$の$f$適用後の総和は、奇数列 $1,3,5,7,9...$ の最初の何項かの総和となっています。

$1,3,5,7,9...$ の最初の$x$項の総和を$g(x)$と定義すると、これは初項$1$・交差$2$・項数$x$の等差数列の総和なので、$g(x) = \frac{(1+(2x-1))x}{2}$ です。
また、制約より$s(k,n)$ は $k \ge 40$ の場合は空集合になります。
よって、この問題の答えは $\displaystyle\sum_{k=0}^{39} g( |s(k,n)| )$ です。※($|s(k,n)|$は$s(k,n)$の要素数です)

$|s(k,n)|$ の求め方

$|s(k,n)| = \frac{n+2^k}{2^{k+1}}$ です。
説明をするのが大変なので省略しますが、$s(k,n)$ の要素を小さい順に並べたものが等差数列である事を利用しています。
32bit整数(C++のint型)では、計算途中にオーバーフローが生じてしまうので、64bit整数を使ってください。

g(x) を求める際の注意

$x$ が大きい場合、 $g(x)$ の分母の$1+(2x-1))x$ が64bit整数の取りうる最大値を超えてしまうことがあります。
つまり、以下のような実装ではWAになります。

$(1+(2x-1))x\ \mathrm{mod}\ 10^9+7$ は、$(1+(2x-1))$ と $x$ をあらかじめmodを取っておくことで、オーバーフローさせずに計算することができますが、その場合計算後の値を2で割るとこれまたWAになります。
つまり、以下のような実装もまずいです。 何故、まずいのかはこの辺の サイト等を参照するといいです。

結論として、2で割る代わりに $\mathrm{mod} 10^9+7$ における$2$の逆元である $2^{(10^9+7) - 2}\ \mathrm{mod}\ 10^9+7 (=500000004)$ を掛けてあげればよいです。

よって、正しく動く $g(x)$ は以下のようになります。

想定解 (C++)

最後に、C++の想定解を載せておきます。

想定解(python)

pythonの場合、多倍長整数が利用可能なため、もっと単純に$g(x)$を求めることが可能になります。