【SSL1343】无限序列

题目描述

思路

可以发现第 (x) 项的长度和 (1) 的个数是斐波那契数列。

然后就设 (dp(x)) 表示 (1sim x-1) 之间多少个 (1)。

又因为 (1) 的个数也是斐波那契数列，那就层层递归就行了！

代码

(dp(x))

#define ll long long

ll dp(ll x)
{
	if(x == 0) return 0;
	
	for(int i = 1; i <= 100; i++)
	{
		if(len[i] == x) return f[i];
		if(len[i] > x) return dp(x - len[i - 1]) + f[i - 1];  
	}
}

( exttt{main()})

int main()
{
	f[1] = f[2] = 1;
	len[1] = 1;len [2] = 2;
	for (int i = 3; i <= 101; i++) f[i] = f[i - 1] + f[i - 2],
								len[i] = len[i - 1] + len[i - 2];
	for (scanf("%d", &q); q--;)
	{
		scanf("%lld%lld", &l, &r);
		printf("%lld
", dp(r) - dp(l - 1));
	}
    return 0;
}