codeforces 126 D Fibonacci SumsプッシュDP

http://www.codeforces.com/problemset/problem/126/D
1つの数がどれだけの種類を表すことができることを求めます   いくつかの非波那且数の和 のシナリオ
まず全体の非波那かつ数の数が少ないことを考慮して、先に処理して、およそ88個で、それから超long longになりました
数学的帰納法を用いて,いずれの正の整数も幾つかの非波那和数の和として表すことができることを実証した.
まず、シナリオの最大の非波那数を見つけることができます. 最大で、後のDPで漏れないようにするためです.
それからDPを始めることができて、私达は1つの特殊なバイナリで私达のさっき得た方案を表すことができます
例えば1000001000001億
2進ビットが1であることは,この非波那且数(左から右へ順次増大)を取ったことを示す.
1つの1は左の2つの1001-』110として表すことができ、ある1の表現方法はcnt/2であり、cntはこの1と前の1との間の0の個数であるため、総案数は乗算原理を利用して左から右に繰り返すことができる.
1つずつ取るか、取らないか、取るには1つの方法しかありません.取らなければ中間のいくつかの1の和を表すことができ、2つの状況に分けて移行すればいいです.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 90;
long long fib[maxn];
long long dp[90][2];
int main()
{
    fib[1]=1;fib[2]=2;
    for(int i=3;i<=88;i++) fib[i]=fib[i-1]+fib[i-2];
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long n;
        scanf("%I64d",&n);
        int b[90],cnt=0;
        for(int i=88;i>=1;i--) if(fib[i]<=n) n-=fib[b[cnt++]=i]; 
        reverse(b,b+cnt);
        //printf("%d %d
",b[0],b[1]);
        dp[0][1]=1;
        dp[0][0]=(b[0]-1)/2;
        for(int i=1;i<cnt;i++)
        {
            dp[i][1]=dp[i-1][0]+dp[i-1][1];
            dp[i][0]=(b[i]-b[i-1]-1)/2*dp[i-1][1]+(b[i]-b[i-1])/2*dp[i-1][0];

        }
        printf("%I64d
",dp[cnt-1][0]+dp[cnt-1][1]);

    }
    return 0;
}