L - 菲波拉契数制升级版
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
我们定义如下数列为菲波拉契数列：
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，请输出把它表示成若干互不相同的菲波拉契数之和有多少种表示法。
Input
第一样一个数T，表示数据组数，之后T行，每行一个数n。
T≤105
1≤n≤1018
Output
输出T行，每行一个数，即n有多少种表示法。
Sample input and output
| Sample Input | Sample Output |
|---|---|
6 |
1 |
解题思路:
首先高位到低位贪心得到基础情况（最好，因为留了最多的操作空间)
dp(i,j) 表示正在决策第 i 位 ( 后面的已经决策完毕 )，且是否取 0->不取，1->取
dp(i,1) = dp(i-1,0) + dp(i-1,1) //取，转移到i-1
不取,那么这一位斐波那契由前面的相加得到
前面一位取了: 因为不能有相同，所以只能分解成 (x-1) / 2 (少了个0) 种情况( x 是前面0的个数 ) -> 00001 -- 00110 -- 11010
前面一位没取: 因为不能有相同，所以只能分解成 x / 2 种情况.
dp(i,0) = dp(i-1,1) *(A-1) + dp(i-1,0) * A;
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
typedef long long ll;
using namespace std;
const int maxn = ;
ll f[maxn];
int dp[maxn][];
vector<int>st; void init_f()
{
f[] = , f[] = , f[] = ;
for(int i = ; i <= ; ++ i)
f[i] = f[i-] + f[i-];
} int main(int argc , char *argv[])
{
init_f();
int Case;
scanf("%d",&Case);
while(Case--)
{
st.clear();
memset(dp,,sizeof(dp));
ll beg;
scanf("%lld",&beg);
int pos = ;
while(beg)
{
if (beg >= f[pos]) // Choose
{
st.pb(pos);
beg -= f[pos];
}
pos--;
}
st.pb();
reverse(st.begin(),st.end()); //高位到低位dp
dp[][] = ; //初始化最高位取1有一种情况.
for(int i = ; i < st.size() ; ++ i)
{
dp[i][] = dp[i-][] + dp[i-][];
int zeronum = st[i] - st[i-] ;
dp[i][] = dp[i-][] * ( (zeronum-) / ) + dp[i-][] * (zeronum / ); //注意加括号，不然出问题!
}
printf("%d\n",dp[st.size()-][] + dp[st.size()-][]);
}
return ;
}