T组数组，求对于每个数，有多少种表示成不同斐波那契数的和的方法。
e.g. 13=13=5+8=2+3+8
首先，每个数是肯定可以表示成斐波那契数类的和的，我们将数用01串表示，1代表取第i位斐波那契数。例如13表示成100000,4表示成101.
同时13也可以表示成11000。即一个1可以拆成低一位和低两位的1。
这里要注意两个个性质
1、第n位的1进行拆分（如果可以拆分）时，第n-1必然是1.这可以由（111111==1010100和11111==101001看出）
2、诸如10000的形式（1后面接n个零），他有[n/2]+1种表示形式，其中将一个1拆分了的形式有[n/2]种
那么我们先预处理，得知10^18范围内我们需要求取88个斐波那契数。然后将每个数表示成斐波那契进制形式，用数组seq[]存储，再进行dp
用两个数组进行dp。dp[i][1]表示保留seq[]第n位数进行表示，dp[i][0]表示不保留seq[]第n位斐波那契，选择将它拆分
显然dp[i][1]=dp[i - 1][1] + dp[i - 1][0];
那么考虑dp[i][0]由什么转移得来
如果seq[]中第i-1位的1拆分了，由性质1知二者的间隔0的数目为seq[i]-seq[i-1]，否则位seq[i]-seq[i-1]-1。再由性质2知第i位的1可以拆分成的数目。然后根据乘法原理，就得到转移式dp[i][0]=seq[i] - seq[i - 1] - 1) / 2 * dp[i - 1][1] + (seq[i] - seq[i - 1]) / 2 * dp[i - 1][0]
（注意上式子中的除二运算是向下取整，所以要先除再乘，一开始这里写错了...)
1 #include2 #include 3 #include 4 #include 5 #define INF 0x3f3f3f3f 6 using namespace std; 7 typedef long long LL; 8 const int maxn = 88; 9 10 LL fib[maxn + 2];11 LL dp[maxn + 2][2];12 int seq[maxn + 2];13 14 int main() {15 fib[1] = 1;16 fib[2] = 2;17 for (int i = 3; i <= maxn; i++) {18 fib[i] = fib[i - 1] + fib[i - 2];19 }20 int T;21 scanf("%d", &T);22 LL N;23 while (T--) {24 scanf("%lld", &N);25 memset(seq, 0, sizeof(seq));26 int cnt = 0;27 for (int i = maxn; i >= 1; i--) {28 if (N >= fib[i]) {29 N -= fib[i];30 seq[cnt++] = i;31 }32 }33 reverse(seq, seq + cnt);34 dp[0][1] = 1;35 dp[0][0] = (seq[0] - 1) / 2;36 for (int i = 1; i < cnt; i++) {37 dp[i][1] = dp[i - 1][0] + dp[i - 1][1];38 dp[i][0] = (seq[i] - seq[i - 1] - 1) / 2 * dp[i - 1][1]39 + (seq[i] - seq[i - 1]) / 2 * dp[i - 1][0];40 }41 printf("%lld\n", dp[cnt - 1][0] + dp[cnt - 1][1]);42 }43 44 return 0;45 }