描述
题解
讨论区大神已经说得十分详细了，我直接拿过来用吧……
实际上这道题可以通过O((logn)^2)的时间推出任意一项。
我们以每一个2的整数次方作为分割点，把这个数列分割成很多块。设F(n)为2^n到2^(n+1)之间的所有满足要求的数字（不包括2^(n+1)）。因为二进制中不能有连续的0，所以F(n)=sigma{
F(k)|0<=k<=n-2}+1，又知F(n-1)=sigma{
F(k)|0<=k<=n-3}+1，可得F(n)=F(n-2)+F(n-1)-1+1=F(n-1)+F(n-2)，因此结论：
有1个数在[1,2)，1个数在[2,4)，2个数在[4,8)，3个数在[8,16)…………
而每次可以用二分查找来确定a的位置在2^m和2^(m+1)之间，a减去[1,2^m]之间所有数的个数，重新递归查找。。。（注意减去的是闭区间！）递归深度不会超过logn，因为它是按斐波那契数列的和递减的。每一次递归的m位置异或1，最后会得到一个01数组，按照进制转换然后求模就行了。。
一共有n个数，对于每一次查找的复杂度是O((logn)^2)，总复杂度不会达到O(n(logn)^2)。这是一个初一的大神写的题解，横戈跃马，他是我认识的人中，年纪和实力最不成比例的人，强的可怕，在他还在 51Nod 上练题时，曾一度占据35名左右，分分钟虐暴***成 ACMer（如果连我也算 ACMer 的话），毕竟搞 ACM 的人中像我这样的炮灰太多了，搞了两年，学会的只是 Orz！
这里需要注意的是，斐波那契数列要求到88位，对应的二进制位数已经超出了 long long 的范围，所以在求 Pow 的过程中要注意取模。当然，在讨论区中，Wizmann 的那句话Magic number here is 88.小心爆long long。就是这个意思，我猜他说的是，在这里魔法数是88？
What’s the ***!!!什么是 Magic number？吓得我赶快百度知乎谷歌了一下~~~这里是一个不错的关于 Magic number 的帖子。
对了，这个题之所以说是数位dp是因为在求 F(n) 的过程中用到了数位dp的思维，另外，这个题里的二分可以直接改成循环，反而会更快，Top 1就是直接循环搞得。
代码
#include <iostream>
using namespace std;
const int MAXF = 88;
const int MOD = 1e9 + 7;
long long Fib[MAXF] = {
1, 1, 2};
long long Pow[MAXF] = {
1, 2, 4};
int XOR[MAXF];
int maxPos = 0;
void init()
{
for (int i = 3; i < MAXF; i++)
{
Fib[i] = Fib[i - 1] + Fib[i - 2];
Pow[i] = Pow[i - 1] * 2 % MOD;
}
}
long long BToD()
{
long long res = 0;
for (int i = 0; i < maxPos; i++)
{
res = (res + XOR[i] * Pow[i]) % MOD;
}
return res;
}
int main(int argc, const char * argv[])
{
init();
int N;
cin >> N;
long long s;
for (int i = 0; i < N; i++)
{
cin >> s;
while (s != 0)
{
int l = 0, r = MAXF;
while (l < r)
{
int mid = (l + r + 1) / 2;
if (Fib[mid] > s)
{
r = mid - 1;
}
else
{
l = mid;
}
}
XOR[l - 1] ^= 1;
maxPos = max(maxPos, l);
s -= Fib[l];
}
}
cout << BToD() << '\n';
return 0;
}
京公网安备 11010502036488号