51nod1379 索函数

果断打表找规律。然后看得出来是2^k-1之后又不知道怎么求出k有什么卵用。。。

http://blog.csdn.net/guhaiteng/article/details/52094210 %%%%神犇的讲解非常详细！

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
ll read(){
	ll x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}
const int mod=1e9+7;
ll Pow(ll a,ll b){
	ll ans=a;--b;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}
ll f[91];
int main(){
	int T=read();
	f[0]=0;f[1]=1;rep(i,2,90) f[i]=f[i-1]+f[i-2];
	while(T--){
		ll n=read();
		if(!n) puts("0");
		else if(n<=90){
			ll len=log(f[n])/log(2);
			printf("%lld
",(Pow(2,len+1)-1+mod)%mod);
		}else{
			ll len=n*log((1+sqrt(5))/2)/log(2)-log(sqrt(5))/log(2);
			printf("%lld
",(Pow(2,len+1)-1+mod)%mod);
		}
	}
	return 0;
}

1379 索函数

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

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