先上题目：
1、无限序列
infinit.pas/c/cpp
1s / 128M
[问题描述]
我们按以下方式产生序列:
1、 开始时序列是: "1" ;
2、 每一次变化把序列中的 "1" 变成 "10" ,"0" 变成 "1"。
经过无限次变化,我们得到序列"1011010110110101101..."。
总共有 Q 个询问,每次询问为:在区间 A 和 B 之间有多少个 1。
请写一个程序回答 Q 个询问。
[输入数据]
第一行为一个整数 Q,后面有 Q 行,每行两个数用空格隔开的整数 a, b。
[输出数据]
共 Q 行,每行一个回答
[输入样例]
1
2 8
[输出样例]
4
[数据范围]
1 <= Q <= 5000
1 <= a <= b < 2^63
------------------------------------------------------------------分割线-----------------------------------------------------------------------
本来一开始一位是要根据数列规律来计算，于是找规律找循环找了半天，最后看了解析才TM地发现居然是斐波那契。。。。。。好吧，先看看下面这几组序列：
1
10
101
10110
10110101
1011010110110
101101011011010110101
......
看了这几个序列是不是发现了什么？对，第i个序列就是在第i-1个序列后面接上第i-2个序列，所以。。。。。。斐波那契。。。。。。
不过要想实现还是需要点思维，必须找到一个斐波那契数f[n]，使得a<=f[n-1]<b<f[n],然后将a，b分为两段，直到每一段的长度都是斐波那契数为止（因为只有这样才能求出第a到第b个数之间的1的个数）
具体还是看下代码吧（其实就是我懒）：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll a,b,f[93],ff[93];
/*切记，斐波那契数到第92个就会爆long long
而这一题的范围正好是long long以内，所以就开到92*/
ll find(ll num,ll x,ll y)
{
if(x==0||y==0) return 0;
if(num==1) return 1;
if(num==2) return x==2?0:1;
if(x==1&&y==f[num]) return ff[num];
ll cnt=0;
if(x<=f[num-1])
{
if(y>f[num-1])
cnt=cnt+find(num-1,x,f[num-1])+find(num-1,1,y-f[num-1]);
else cnt+=find(num-1,x,y);
}
else cnt+=find(num-2,x-f[num-1],y-f[num-1]);
return cnt;
}
int main()
{
freopen("infinit.in","r",stdin);
freopen("infinit.out","w",stdout);
scanf("%lld",&n);
f[1]=ff[1]=1;
f[2]=2;ff[2]=1;
for(ll i=3;i<=92;i++)
{
f[i]=f[i-1]+f[i-2];
ff[i]=ff[i-1]+ff[i-2];
}
for(ll i=1;i<=n;i++)
{
scanf("%lld%lld",&a,&b);
ll ans=find(92,a,b);
printf("%lld
",ans);
}
return 0;
}