[數值遞推]NOIP模擬題 ：產生01串 infinit 解題報告

【問題描述】

我們按以下方式產生序列：

1、 開始時序列是： " 1 " ；

2、 每一次變化把序列中的 " 1 " 變成 " 10 " ，" 0 " 變成 " 1 "。

經過無限次變化，我們得到序列" 1011010110110101101... "。

總共有 Q 個詢問，每次詢問爲：在區間A和B之間有多少個1。

任務 寫一個程序回答 Q個詢問

輸入 第一行爲一個整數 Q，後面有Q行，每行兩個數用空格隔開的整數 a , b 。

輸出 共 Q行，每行一個回答

約定

1 <= Q <= 5000

1 <= a <= b < 2^63

樣例

infinit.in	infinit.out
1 2 8	4

測試數據下載：http://zyf.ucoz.net/testdata/infinit.rar

【分析】

S1 = "1"
S2 = "10"
S3 = "101"
S4 = "10110"
S5 = "10110101"

Si 是 S(i+1)的前綴。

序列Si 是由序列 S(i-1)和S(i-2), 連接而成的。

即Si = S(i-1)+S(i-2) (實際上是Fibonacci數列)。

找到規律以後，可以先求出從位置1到位置X之間所有的1的個數。

用一個函數F計算，結果爲f(b)-f(a-1)。

每一項1的個數以及每一項的長度都符合數列規律.長度的第93項恰好大於2^63,所以遞推到92項即可  

 【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
unsigned long long F[95];
unsigned long long L[95];

unsigned long long Getm(unsigned long long  x)
{
    int i1;
    unsigned long long getm=0;
    while(x!=0)
    {
        for(i1=1;i1<=92;i1++)
        {
            if(L[i1]>x)
            {
                getm+=F[i1-1];
                x-=L[i1-1];
                break;
            }
        }
    }
    return getm;
}

int main()
{
    freopen("infinit.in","r",stdin);
    freopen("infinit.out","w",stdout);
   
    F[0]=0;
    F[1]=1,L[1]=1;
    F[2]=1,L[2]=2;
    for (int i=3;i<=92;i++)
    {
        F[i]=F[i-1]+F[i-2];
        L[i]=L[i-1]+L[i-2];
    }
    int N;
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
    {
        unsigned long long a,b;
        cin>>a>>b;
        a--;
        cout<<Getm(b)-Getm(a)<<endl;
    }
    return 0;
}