求所有可以只用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;
}
#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;
}
