数列】"/>
无限序列【斐波那契数列】
>Description
我们按以下方式产生序列:
1、 开始时序列是: “1” ;
2、 每一次变化把序列中的 “1” 变成 “10” ,“0” 变成 “1”。
经过无限次变化,我们得到序列"1011010110110101101…"。
总共有 Q 个询问,每次询问为:在区间A和B之间有多少个1。
任务 写一个程序回答Q个询问
>Input
第一行为一个整数Q,后面有Q行,每行两个数用空格隔开的整数a, b。
>Output
共Q行,每行一个回答
>Sample Input
1
2 8
>Sample Output
4
1 <= Q <= 5000
1 <= a <= b < 2^63
>解题思路
列举以后可以发现规律:
每第(i)次变化得来的数列为第(i-1)次+第(i-2)次——也就是斐波那契数列
所以,相同地,第(i)个数列中1的数量为第(i-1)次+第(i-2)次。
由于a ~ b可以看为:(1~b) - (1 ~ a-1),前缀和,
然后,1~i的数列中1的个数,可以看成是经过某两次变化得来的1的个数的和(a+b),其中这分别两次变化得来的数列的长度的和必须为i。
>代码
#include<iostream>
#include<cstdio>
using namespace std;
int n;
long long aa,bb,f[100],c[100];
long long ooo(long long cc)
{for(int i=1;i<=92;i++)if(c[i]==cc) return f[i];else if(c[i]>cc) return f[i-1]+ooo(cc-c[i-1]);
}
int main()
{scanf("%d",&n);f[1]=f[2]=1; //f[i]记录第i个数列中1的个数c[1]=1; c[2]=2; //c[i]记录第i个数列的长度for(int i=3;i<=92;i++)f[i]=f[i-1]+f[i-2],c[i]=c[i-1]+c[i-2]; //斐波那契数列for(int i=1;i<=n;i++){scanf("%lld%lld",&aa,&bb);long long li=ooo(bb),sa;if(aa-1==0) sa=0; //如果数列为1~bb的话就只用求bbelse sa=ooo(aa-1);printf("%lld\n",li-sa); }return 0;
}
更多推荐
无限序列【斐波那契数列】
发布评论