SSL 1861 JZOJ 1365 无限序列

SSL比赛

---

纪中比赛

---

题目

求一个序列中的一个区间有多少个1。

---

分析

1011010110110101101……
1
10
101
10110
10110101
……
我们可以观察到这些序列的1的个数都是斐波那契数，然后长度也是斐波那契数。
so

---

代码

#include <cstdio>
#include <cctype>
#include <map>
#define ull unsigned long long
using namespace std;
ull t,a,b,f[101],num[101]; map<ull,ull>uk;
ull in(){//逐字符输入
    ull ans=0; char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans;
}
void print(ull x){//逐字符输出
    if (!x) return; else print(x/10);
    putchar(x%10+48);
}
ull ans(ull x){
    if (uk[x]) return uk[x];//map
    ull sum=0,y=x; int i;
    while (y){
    for (i=1;f[i]<=y;i++); i--;
    y-=f[i]; sum+=f[i-1];//寻找最大的斐波那契数
    }
    return uk[x]=sum;
}
int main(){
    t=in(); f[1]=1; f[2]=1;
    for (int i=3;i<=100;i++) f[i]=f[i-1]+f[i-2];//斐波那契
    while (t--){
        a=in(); b=in();
        ull s=ans(b)-ans(a-1);//前缀和
        if (s) print(s); 
        else putchar('0');
        putchar('\n');
    }
    return 0;
}