데이터가 매우 커서 가방의 사고방식으로 수조를 열 수 없다.
먼저 피폴라 계수, 예를 들어fib(i)의 표현법을 순서대로 고려하고 i가 비교적 크다고 가정하면 피폴라 계수의 정의로fib(i)=fib(i-1)+fib(i-2)를 알 수 있다.다른 표현을 찾으려면 fib(i-1)나fib(i-2)를 계속 분할해야 한다. 만약에 분할fib(i-1)가fib(i)=2*fib(i-2)+fib(i-3)를 얻으면,이것은 서로 다른 성질을 보장할 수 없다(보충, 아마도 이 식을 중간 과정으로 삼아 모순항을 뜯어내어 유일성을 확보하는 것을 고려할 것이다. 그러나 하나의 모순을 없애면 반드시 새로운 모순이 생기기 때문에 안 된다. 구체적으로 말하면fib(i-2)=fib(i-3)+fib(i-4)를fib(i-2)의 모순을 없애고fib(i-3)의 모순이 생긴다. fib(i-3)는fib(i-1)에서 얻어서 유한한 분할을 통해 모순을 없앨 수 없다).따라서fib(i-2)를 뜯어보고 표현방식fib(i)=fib(i-1)+fib(i-3)+fib(i-4)를 얻는다.계속 나누면 앞과 유사하게fib(i-4)만 뜯을 수 있습니다.매번 최소fib수만 뜯을 수 있고 종점은fib(1) 또는fib(2)인 것을 발견하기 어렵지 않다.상기 과정에서 알 수 있듯이 1 또는 2+2*m=i, m는fib(i) 자체를 제외한 다른 표시 방법이고 상식에서 m=(i-1)/2(/모두 아래로 정돈하고 아래는 동일)을 나타낼 수 있다.ok, 우리는 n이 피폴라 계수인 상황을 성공적으로 해결했다.다음은 n이 피폴라 계수인 조합의 상황을 고려한다.n=fib(i)+fib(j), i>j를 가정하기;우리는fib(i)와fib(j)의 단독 상황을 알고 있다. 현재 조합하면 방금 분리된 사상을 참고할 수 있다. 다른 것은 현재fib(i)와fib(j)가 모두 분리될 수 있다는 것이다.가령 fb(j)를 분해한다고 가정하면 (왜 작은 것을 분해해야 하는지 물어볼 수도 있다. 왜냐하면 fb(i)분해에서fib(j)분해와 충돌하는 상황이 있기 때문이다) (j-1)/2+1조를 얻을 수 있기 때문이다.현재fib(i)를 뜯는 것을 고려하면 처음과 같은 사상은 종점에 변화가 생겼을 뿐이다. 종점(독립성을 확보하기 위해fib(j)의 분할 상황을 고찰한 결과 (j-1)/2가지 분할에서fib(j-1)로 시작하는 것을 발견했다. 따라서 종점은fib(j) 또는fib(j+1)로 등식2*m1+j 또는(j+1)=i,m1=(i-j)/2,m1은fib(i) 자체를 제외한 다른 표현 방법이다.fib(j)로 시작하여fib(j) 자체, 종점은fib(j+1) 또는fib(j+2), m2=(i-j-1)/2, m2는fib(i) 자체를 제외한 다른 표현 방법이다.종합하면fib(i)를 포함하는 표시는 (j-1)/2+1종,fib(i)를 포함하지 않는 표시는 m1*(j-1)/2+m2가 있다.현재 n=fib(i)+fib(j)+fib(k), i>j>k로 확대된 상황fib(j)와fib(k)의 조합은 이미 알고 있으며, 두 조로 나뉘어fib(j)로 시작하는 것과fib(j-1)로 시작하는 것,fib(i)에 대한 분할은 이전 방법과 같다. 이로써 dp[i][0]의 정의를 내린다.fib(i-1)로 시작하는 모든 조합, dp[i][1]:fib(i)로 시작하는 모든 조합이다.그래서 상태 이동 방정식 dp[i][1]=dp[j][0]+dp[j][1], dp[i][0]=(i-j-1)/2*dp[j][1]+(i-j)/2*dp[j][0]가 있고 최종 결과는 dp[maxi][0]+dp[maxi][1]이다.
 

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;



long long int dp[88][2];//dp[i][0]   comb[0~i]            fib[i-1]    [1]   fib[i]   

long long int fib[88];



void get_fibs()

{

  fib[0]=1;fib[1]=1;

  for(int i=2;i<88;i++)

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

}

vector<int> comb;//  n fib   

long long int n;

void solve()

{

  comb.clear();

  for(int i=87;i>0&&n;i--)

    if(n>=fib[i])

    {

      n-=fib[i];

      comb.push_back(i-1);

    }

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

    dp[0][1]=1;

    dp[0][0]=comb[0]/2;

    for(int i=1;i<comb.size();i++)

    {

      dp[i][1]=dp[i-1][0]+dp[i-1][1];

      dp[i][0]=(comb[i]-comb[i-1]-1)/2*dp[i-1][1]+(comb[i]-comb[i-1])/2*dp[i-1][0];

    }

    printf("%lld
",dp[comb.size()-1][1]+dp[comb.size()-1][0]);

}



int main()

{

  get_fibs();

  int T;

  scanf("%d",&T);

  while(T--)

  {

    scanf("%lld",&n);

    solve();

  }

  return 0;

}