Time Limit: 5 Sec  Memory Limit: 128 MBSubmit: 670  Solved: 387[Submit][Status][Discuss]Description       第二关和很出名的斐波那契数列有关，地球上的OIer都知道：F1=1, F2=2, Fi = Fi-1 + Fi-2，每一项都可以称为斐波那契数。现在给一个正整数N，它可以写成一些斐波那契数的和的形式。如果我们要求不同的方案中不能有相同的斐波那契数，那么对一个N最多可以写出多少种方案呢？Input       只有一个整数N。Output       一个方案数Sample Input       16Sample Output       4HINTHint：16=3+13=3+5+8=1+2+13=1+2+5+8对于30%的数据，n<=256对于100%的数据，n<=10^18Source

好题，很有意思。

第一反应是斐波那契数在1e18内不多，从大到小，贪心地选数。一个数能选的话，后面也一定能选，但不一定有第一处优，所以能选就选。

这样的构造是唯一的。

然后就是问题了， 对于这样的一个序列，任何一项a[i]都可以被a[i-1]和a[i-2]替代，需要求替代的方案数，也就是答案了。

这里卡住了，dp的威力就在此了。

f[i][0/1]表示a序列第i个数不替换/替换的方案数

f[i][1]=f[i-1][0]+f[i-1][1]

f[i][0]=f[i-1][0] * ((a[i]-a[i-1])/2)+f[i-1][1] * ((a[i]-a[i-1]-1)/2)

记得开longlong

#include
    
     #include
     
      #include
      
       using namespace std;typedef long long ll;const int MAXN=1005;ll f[MAXN][2],fib[MAXN],n;ll a[MAXN],p;const int TOP=88;int main(){    fib[1]=1;fib[2]=2;    for(int i=3;i<=TOP;i++) fib[i]=fib[i-1]+fib[i-2];    cin>>n;    ll sav=n;//    for(int i=TOP;i>=1;i--){        if(!sav) break;        if(sav>=fib[i]) {            a[++p]=i;            sav-=fib[i];        }    }    if(sav) return cout<<0,0;    sort(a+1,a+1+p);    f[1][1]=1;    f[1][0]=(a[1]-1)/2;    for(int i=2;i<=p;i++){        f[i][1]=f[i-1][0]+f[i-1][1];        f[i][0]=f[i-1][0]*((a[i]-a[i-1])/2)+f[i-1][1]*((a[i]-a[i-1]-1)/2);    }    cout<