菲波拉契数制

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

我们定义如下数列为菲波拉契数列：

F(1)=1F(1)=1

F(2)=2F(2)=2

F(i)=F(i−1)+F(i−2)(i>=3)F(i)=F(i−1)+F(i−2)(i>=3)

给定任意一个数，我们可以把它表示成若干互不相同的菲波拉契数之和。比如1313有三种表示法

13=1313=13

13=5+813=5+8

13=2+3+813=2+3+8

现在给你一个数nn，请输出把它表示成若干互不相同的菲波拉契数之和有多少种表示法。

Input

第一样一个数TT，表示数据组数，之后TT行，每行一个数nn。

T≤105T≤105

1≤n≤1051≤n≤105

Output

输出TT行，每行一个数，即nn有多少种表示法。

Sample input and output

Source

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <map>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

typedef  long long  ll;

typedef unsigned long long ull;

#define MM(a,b) memset(a,b,sizeof(a));

#define inf 0x7f7f7f7f

#define FOR(i,n) for(int i=1;i<=n;i++)

#define CT continue;

#define PF printf

#define SC scanf

const int mod=1000000007;

const int N=1e5+100;

int dp[N],a[N];

int main()

{

    MM(dp,0);

    a[1]=1;a[2]=2;

    int cnt=3;

    for(;a[cnt-1]<=1e5;cnt++)

         a[cnt]=a[cnt-1]+a[cnt-2];

    cnt-=2;

    dp[0]=1;

    for(int i=1;i<=cnt;i++)

        for(int j=100000;j>=a[i];j--)

         dp[j]+=dp[j-a[i]];

    int n,cas;

    scanf("%d",&cas);

     while(cas--)

     {

       scanf("%d",&n);

       printf("%d\n",dp[n]);

     }

    return 0;

}

　　错因分析：这道题想到了直接统计，比如1有一种组成方式，2有一种，那么因为3=1+2，所以3=两种

5=2+3，所以5也有两种.....但是无法处理数字重复使用的情况，比如13=5+8，但是5=3+2,8=5+3

这样的话那么3很有可能被重复使用，但是数字又不能出现重复。。。所以就没办法了。。

所以统计走不通的话，就只有改成构造了，枚举一下斐波那契数能构造出来的数，细心可以发现斐波那契数大概也就20多个的样子（在<=1e5范围内）。

契数