首页 > 代码库 > 51nod1379 索函数
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 longll 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\n",(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\n",(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示例
212
Output示例
11
51nod1379 索函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。