[數學遞推]OI練習題：Binacy

【題目描述】

求所有可以只用1和00拼成的長度爲N的二進制數的個數除以1 5746的餘數。

比如當N=4的時候，有5個可能的二進制：0011，0000，1001，1100，1111。

【輸入格式】

第一行一個正整數N

【輸出格式】

輸出所有可以只用1和00拼成的長度爲N的二進制數的個數除以15746的餘數。

【輸入樣例】

4

【輸出樣例】

5

【數據範圍】

在100％的數據中，1≤N<1000000

【分析】

先嘗試寫出前幾個，找找規律：

N=0時 結果為0

N=1時 結果為1

N=2時 結果為2

N=3時 結果為3

N=4時 結果為5

......

可以看出，這是斐波那契數列。

所以，只需要遞推出斐波那契數列即可。

遞推式：

               S[0]=0,S[1]=1,

               S[2]=2;

               S[n]=S[n-2]+S[n-1] (n>2)

【代碼】

這是我以前的代碼，不知道我當時為何要把前幾個數打成表。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
unsigned long long S[1000001];
int main()
{
    freopen("binacy.in","r",stdin);
    freopen("binacy.out","w",stdout);
    int N;
    cin>>N;
    if(N<=4)
    {
        switch(N)
        {
        case 0:
            cout<<0<<endl;
            break;
        case 1:
            cout<<1<<endl;
            break;
        case 2:
            cout<<2<<endl;
            break;
        case 3:
            cout<<3<<endl;
            break;
        case 4:
            cout<<5<<endl;
            break;
        }
        return 0;
    }
    S[3]=3;
    S[4]=5;
    for (int i=5;i<=N;i++)
        S[i]=(S[i-1]+S[i-2])%15746;
    cout<<S[N]<<endl;
    return 0;
}