題目連結：
題目大意：
給定一二進位制正整數 Ｌ （１ ≦ 其在十進位制下的值 ≦ ２ ^ ９２３, ０００，且沒有前導 ０ ），求有多少對（ａ, ｂ）數對滿足：
ａ ＋ ｂ ≦ Ｌ 且
ａ ＸＯＲ ｂ ＝ ａ ＋ ｂ
由於答案可能很大，請將答案取除以 １０ ^ ９ ＋ ７ 之後的餘數。
範例輸入：
第一筆:
10
第二筆:
1111111111111111111
第三筆:
1
範例輸出：
第一筆:
5
第二筆:
162261460
第三筆:
3
解題思維：
我們先觀察如果數對 （ａ, ｂ） 滿足 ａ ＋ ｂ ＝ Ｌ ，有多少數對 （ａ, ｂ） 滿足 ａ ＋ ｂ ＝ ａ ＸＯＲ ｂ 。而我們可以發現其即跟 Ｌ 中有多少的 １ 有關，設其 １ 的數量為 Ｃ 。則有 ２ ^ Ｃ 個數對滿足要求。因為每個「1」可以分給 ａ 或是 ｂ 。
接著推廣成題目的樣子就是把所以對於 ａ ＋ ｂ ＝ Ｎ （０ ≦ Ｎ ≦ Ｌ），求每個 Ｎ 中 １ 的數量 ＣＮ 並將所有值加總起來。但是直接做當然會超時（Ｌ 值太大了）。
因此，我們需要可以快速統計 ≦ Ｌ 的數字中 ２ ^ ＣＮ 之總和的方法。有一方法如下所示：
設我們現在的Ｌ值為 ｂ０ ｂ１ ｂ２ …… ｂｎ－１ （每個 ｂｉ 代表 Ｌ 中的一個位數），因此 ｂ０ 一定為 １ 所以以 ｂ０ 為例：
我們可以發現 ≦ １ ０ ０ …… ０ 的數字有 ２ ^ （ｎ－１） 個，而它們的 ２ ^ ＣＮ 總和為
而上式即為 （２ ＋ １） ^ （ｎ － １） 的二項式展開，所以值為 ３ ^ （ｎ － １） 。
而接著如果 ｂ１ 也為 １ ，則結果也類似 ｂ０ 的情況，但是這次 ≦ ｂ０ １ ０ …… ０ 有 ２ ^ （ｎ － ２）且計算 ２ ^ ＣＮ 的總和考慮前面有的「１」之數量（對於 ｂ１ 來說，有 ｂ０ 這１ 個「１」），因此代入上式後算出來的 ２ ^ ＣＮ 之總和應為
３ ^ （ｎ － ２ ） × ２
推廣一下，可得通式：
ｂｉ × ３ ^（ｎ － ｉ － １） × ２ ^ Ｏｉ
其中， Ｏｉ 代表 ｂｉ 的左邊位數有多少個「１」（不過不包含 ｂｉ 自己）。
因此，由左至右掃過 Ｌ 的位元即可求得解答。至於要快速地算出 ３ 的次方，可以使用「快速冪」的技巧，詳情參見本人一年前的文章。
但是由於上面的算法不會考慮到 ａ ＋ ｂ ＝ Ｌ 的情況，因此還要再將其值加入答案裡，即 ２ ^ Ｏｉ 。
另外，上面的每個運算之後都要記得取 １０ ^ ９ ＋ ７ 的餘數。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人