1508: ZZ’s Fibonacci Problem

http://www.acmore.net/problem.php?id=1508

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 67 Solved: 14

Description

　　　ZZ is a big fan of Fibonacci numbers, and she pays lots of attention on Fibonacci numbers, Fibonacci numbers have the following form: F(1) = 1, F(2) =2, F(i) = F(i-1) + F(i-2), i > 2. ZZ is a so clever girl, she found some interested things, a non-empty set S = { s1,s2……sk }, consisting of different Fibonacci numbers, the sum of this set’s elements call the set S a number n’s decomposition into Fibonacci sum. It’s easy to see that the numbers have several decompositions into Fibonacci sum, for example, for 13 we have 13, 5 + 8, 2 + 3 + 8 three decomposition, and for 16,3 +13, 1 + 2 +13 , 3 + 5 + 8, 1 + 2 + 5 + 8 --- four decompositions . ZZ is so happy of find this, but what's a pity, ZZ don’t know how to find the number of the possible different decompositions into Fibonacci sum if give a number n ? Can you help her?

Input

The input contains several test cases,The first line of each test case consists of an integer t — the number of tests (1≤t≤10⁵),next t lines contain an integer n (1≤n≤10¹⁸).

Output

For each input data test print a single number on a single line — the answer to the problem.

Sample Input

2 13 16

Sample Output

3 4

HINT

Source

2013ACM多校联合(4)_NUN

这题首先要找到每一个数的这样一种分解：任何一个数都能够被唯一分解成不相邻的若干个菲波那契数之和。如果把分解看作是是否第i个菲波那契数的向量的话。也就是1的数量最少的一个向量。对于题中所要求计算的其他分解方式就是在这个基础上进行的，问题转化为某一位的1分或者是不分。

例如：105 = 3 + 13 + 89 对应于向量 0010010001。

设状态dp[i][0]表示第i个菲波那契数进行不进行分解的方案数，dp[i][1]表示第i个菲波那契数进行分解。这里有这样一个推论：某一个1有多少种分解是一个其前面有多少个0的函数。

例如考虑 0000001 存在这样的分解路线 0000001 -> 0000110 -> 00110100 -> 11010100

观察到每一分解后一个1总是无法再往前移动的，而只有前面一个1能够往前移动，如果0的个数为x的话，移动的次数恰好为x/2。

如此便有动态规划方程：

dp[i][1] = dp[i-1][0] + dp[i-1][1]
dp[i][0] = dp[i-1][0] * （相邻1之间0的个数加1）/2 + dp[i-1][1] *（相邻1之间0的个数）/2

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

long long fi[90];
long long N;
int dp[90][2];
int idx,a[90];

void Init(){
    fi[0]=fi[1]=1;
    for(int i=2;i<=86;i++)
        fi[i]=fi[i-1]+fi[i-2];
}

void swap(int &x,int &y){
    int tmp=x;x=y;y=tmp;
}

void Solve(){
    idx=1;
    for(int i=86;i>=1;i--)
        if(N>=fi[i]){
            N-=fi[i];
            a[idx++]=i;
        }
    for(int i=1,j=idx-1;i<j;i++,j--)
        swap(a[i],a[j]);

    memset(dp,0,sizeof(dp));
    dp[0][1]=1;
    for(int i=1;i<idx;i++){
        dp[i][1]=dp[i-1][0]+dp[i-1][1];
        dp[i][0]=dp[i-1][1]*((a[i]-a[i-1]-1)/2)+dp[i-1][0]*((a[i]-a[i-1])/2);
    }
    printf("%d\n",dp[idx-1][0]+dp[idx-1][1]);
}

int main(){

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

    Init();
    int t;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%lld",&N);
            Solve();
        }
    }
    return 0;
}