51nod1379 索函数

Fib[0]=0,Fib[1]=1,Fib[n]=Fib[n-1]+Fib[n-2] if n>1.

定义索函数Sor(n)=Fib[0]| Fib[1] |Fib[2]|…|Fib[n].

给定整数n，要求计算Sor(n)%1,000,000,007(1e9+7).

Input

第1行：给出一个整数T，表示有T组数据。(1<=T<=10000)
第2行到T+1行，每行一个整数n。(0<=n<=10^10)

Output

对于每个测试用例，输出结果占一行。

Input示例

2
1
2

Output示例1

1
分析：斐波那契数列增长速度非常快，打个表可以发现Sor函数有很多数每一位都是1，找个规律可以发现
，关键就是怎么求位数.直接递推会T掉，矩阵快速幂会非常麻烦，可以用通项公式.，当n足够大的时候，求位数的话取一下log就好了.

#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

ll T, n, f[110];

ll qpow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

void init()
{
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= 90; i++)
        f[i] = f[i - 1] + f[i - 2];
}

int main()
{
    scanf("%lld", &T);
    init();
    while (T--)
    {
        scanf("%lld", &n);
        if (n == 0)
            printf("0
");
        else
        if (n <= 90)
        {
            ll temp = log(f[n]) / log(2.0);
            printf("%lld
", qpow(2, temp + 1) - 1);
        }
        else
        {
            ll temp = n * log((1 + sqrt(5)) / 2) / log(2.0) - log(sqrt(5)) / log(2.0);
            printf("%lld
", qpow(2, temp + 1) - 1);
        }
    }

    return 0;
}