Counting 1's (AOJ 2539) - あああああ

$b_i(x)$ を $x$ を 2 進数表記したときに下から $i$ bit 目 (1-indexed) が立っているなら 1 を, そうでないなら 0 を返す関数とする。

A と B を $1 \le A \le B \le 1e18$ を満たす整数とし、 $k_i$ を $A \le x \le B$ かつ $b_i(x) = 1$ となる整数 $x$ の数とする。

$k_i$ が与えられるので、A と B を求めてください。

ただし、答えが複数あるなら Many を、1 つもないなら None を出力すること。

マルチテストケース

テストケース数は 100000 個以下

$1 \le n \le 64$

入力では $k_1 , k_2 , ... , k_n$ のみ与えられる。

$i \le n$ のとき $0 \le k_i \le 2^{63} - 1$

$n \lt i$ のとき $k_i = 0$

$k_1$ を見ることで、 $B-A$ の値は高々 3 通りに絞ることができる。

$B-A$ を固定したとき、 $(A+B) (B-A+1) / 2 = \sum 2^{i-1} k_i$ を利用すると、A, B が求められる。

あとは、それぞれ $k_i$ を実際に計算して確かめればよい。

解説とか(公開)コードを読むと $\sum 2^{i-1} k_i$ を計算してる人が見当たらなくて桁ごとになんかやってたので別解チャンスと思って書きました、がどうせ $k_i$ を確かめると思うとそんなに楽になってないかも