先考虑一个斐波那契数能分成其他斐波那契数的方案，假如f[i]表示第i个斐波那契数，那么只要对他进行拆分，f[i-1]这个数字必定会存在。知道这一点就可以进行递推了。先将数字分成最少项的斐波那契数之和，s[i]表示第i项的数字对应的斐波那契数编号，F[i]表示对不第i项进行拆分，G[i]表示对第i项进行拆分，g[i]表示对编号为i的斐波那契数拆分的话，有多少种方案。那么可以得到递推式:
F[i]=F[i-1]+G[i-1];
G[i]=F[i-1]*(g[s[i]-s[i-1]])+G[i-1]*(g[s[i]-s[i-1]+1]);
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#define N 1000010
#define P 100000007
using namespace std;
long long n,f[N],Q,ans,g[N],F[N],G[N];
int s[N],tot;
int i;
int main()
{
f[]=;
f[]=;
Q=;
Q=Q*Q;
for (i=;i<=;i++)
{
f[i]=f[i-]+f[i-];
if (f[i]>Q) break;
}
g[]=;
for (i=;i<=;i++)
if (i%)
g[i]=g[i-]+;
else
g[i]=g[i-];
for (i=;i<=;i++)
g[i]--;
int test;
scanf("%d",&test);
while (test)
{
test--;tot=;
scanf("%I64d",&n);
for (i=;i>=;i--)
if (n-f[i]>=)
{
tot++;s[tot]=i;
n=n-f[i];
}
ans=;
F[tot]=;
G[tot]=g[s[tot]];
for (i=tot-;i>=;i--)
{
F[i]=F[i+]+G[i+];
G[i]=F[i+]*(g[s[i]-s[i+]])+G[i+]*(g[s[i]-s[i+]+]);
}
printf("%I64d\n",F[]+G[]);
}
}