Contest20140906 ProblemC 菲波拉契数制 DP

C.菲波拉契数制
时间：2s   内存：65536KB
我们定义如下数列为菲波拉契数列：
                    F (1) = 1
                    F (2) = 2
                    F (i) = F(i-1)+F(i-2) (i>=3)
给定任意一个数，我们可以把它表示成若干不同的菲波拉契数之和。比如13有三种表示法
13=13
13=5+8
13=2+3+8
现在给你一个数n，请输出把它表示成若干不同的菲波拉契数之和有多少种表示法。

输入：
第一样一个数T，表示数据组数，之后T行，每行一个数n。
20%的数据:T<=10,n<=30
60%的数据:T<=100,n<=100000
100%的数据：T<=10^5, n<=10^18

输出：
输出T行，每行一个数，即n有多少种表示法。

样例：

输入：
6
1
2
3
4
5
13

输出：
1
1
2
1
2
3

这种DP很不容易看出想出状态，我在考试的时候大部分时间都用在这道题上了，评讲时也证明我基本上已经想了90%的正解，只有一个我没有想到，即最大表示后每一项后移步数不超过1。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<string>

#include<queue>

#include<stack>

using namespace std;

#ifdef WIN32

#define LL "%I64d"

#else

#define LL "%lld"

#endif

typedef long long qword;

typedef long long number;

#define MAXF 110

#define MAXN 110000

#define PROB "C"

qword fib[MAXF];

int topf;

vector<int> vec;

void init()

{

        int i;

        fib[]=fib[]=;

        for (i=;fib[i-]<1000000000000000000LL;i++)

        {

                fib[i]=fib[i-]+fib[i-];

        }

        topf=i-;

}

qword f[MAXF][];

int a[MAXF];

qword n,m;

int main()

{

        //freopen("input.txt","r",stdin);

        //freopen("output.txt","w",stdout);

        freopen(PROB".in","r",stdin);

        freopen(PROB".out","w",stdout);

        int i,j,k;

        int x,y,z;

        int nn;

        scanf("%d",&nn);

        init();

        while (nn--)

        {

                scanf(LL ,&n);

                vec.clear();

                for (i=topf;i>;i--)

                {

                        if (fib[i]<=n)

                        {

                                n-=fib[i];

                                vec.push_back(i);

                        }

                }

                sort(vec.begin(),vec.end());

                for (i=;i<vec.size();i++)

                {

                        a[i]=(-((i)?vec[i-]:)+vec[i]);

                }

                f[][]=;

                f[][]=a[]/;

                for (i=;i<vec.size();i++)

                {

                        f[i][]=((a[i]-)/)*f[i-][]+((a[i])/)*f[i-][];

                        f[i][]=f[i-][]+f[i-][];

                }

                printf("%lld\n",f[vec.size()-][]+f[vec.size()-][]);

        }

        return ;

}