51nod1379 索函数

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 #include #include #include #include #include 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\n"); else if (n <= 90) { ll temp = log(f[n]) / log(2.0); printf("%lld\n", 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\n", qpow(2, temp + 1) - 1); } } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。