SSL_1861 无限序列

题意：

    有一个序列，初始状态是“1”，每次都可以让序列中的“1”变成“10”，让“0”变成“1”，最后可以得到"1011010110110101101..."求这个序列的a到b中一共有多少个“1”。

思路：

    找规律可以发现这个字符串每次操作都是加上前两次的字符串，类似斐波那契的算法，例如“101”是从“10”+“1”得来的，下一个字符串就是“101”加上前一个“10”变成“10110”，我们根据这些字符串可以知道第几次操作时这些字符串的长度和它们当前共有几个“1”，然后用就可以用递归去查找a到b中“1”的个数了。

代码：

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
long long ans,a,b,t,l[100],d[100];
long long __Ans(long long x,long long y)//求前x个数点的个数
{
	if (x==0) return 0;
	if (x==l[y]) return d[y];//如果长度相等那可以直接返回我们之前初始化1的个数
	else
    if (x<=l[y-1]) return __Ans(x,y-1);//如果x在l[y-1]内，我们就在y-1次操作时求
    else return d[y-1]+__Ans(x-l[y-1],y-2);//如果不在里面，答案就是上一次操作时点的个数加上上上次操作的个数，因为字符串是从前两个加起来的
}
int main()
{
	d[1]=1;l[0]=1;l[1]=1;//d存i次操作时1的个数，l存长度
	for (int i=2;i<=92;i++)//初始化，因为斐波那契做到92的时候就会超出范围了
	{
		l[i]=l[i-1]+l[i-2];
		d[i]=d[i-1]+d[i-2];
	}
	scanf("%lld",&t);
	while (t--)
	{
		ans=0;
		scanf("%lld%lld",&a,&b);
		printf("%lld\n",__Ans(b,92)-__Ans(a-1,92));//用1~b的那一段-1~a的那一段就可以得出a~b的答案
	}
	return 0;
}