//昨天在姜神的提醒下发现这种方法可以解决升级版的 非升级版直接01背包就好
//这题脑洞开得真是够大
解：大概要先把数分解成斐波拉契进制，x=f1*(0或1)+f2*(0或1)+...+fn*(0或1) f1表示第一个斐波拉契数字（和二进制分解很像 但是这里要分解成斐波拉契进制）
然后如果一个数分解后某三位位上为100 那么可以将其拆分为011（再拆01011 0101011）
于是有dp[i][0]代表某一位不拆 dp[i][1]代表某一位拆a[i]代表第i个1后面有多少0，于是
dp[i][0] += dp[i - 1][0] + dp[i - 1][1];
dp[i][1] += dp[i - 1][0] * (a[i] / 2) + dp[i - 1][1] * ((a[i] + 1) / 2);
//那个a[i]/2自己画出来看看就知道了 很显然的
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #include<stack> 11 #include<string> 12 13 using namespace std; 14 15 long long T; 16 long long f[100]; 17 long long dp[100][2]; 18 long long a[100]; 19 long long cnt; 20 21 void get_a(long long x){ 22 long long e[100]; 23 memset(e,0,sizeof(e)); 24 for (long long i=90;i>=1;i--){ 25 if (x>=f[i]){ 26 e[i]=1; 27 x-=f[i]; 28 } 29 } 30 long long tmp=0; 31 cnt=0; 32 memset(a,0,sizeof(a)); 33 for (long long i=1;i<=90;i++){ 34 if (e[i]==1){ 35 a[++cnt]=tmp; 36 tmp=0; 37 } 38 else{ 39 tmp++; 40 } 41 } 42 } 43 44 45 int main(){ 46 f[0]=1; 47 f[1]=1; 48 for (long long i=2;i<=90;i++) f[i]=f[i-1]+f[i-2]; 49 scanf("%lld",&T); 50 for (long long cas=0;cas<T;cas++){ 51 long long x; 52 scanf("%lld",&x); 53 get_a(x); 54 memset(dp,0,sizeof(dp)); 55 dp[1][0]=1; 56 dp[1][1]=a[1]/2; 57 for (long long i=2;i<=cnt;i++){ 58 dp[i][0]=dp[i-1][0]+dp[i-1][1]; 59 dp[i][1]=dp[i-1][0]*(a[i]/2)+dp[i-1][1]*((a[i]+1)/2); 60 } 61 printf("%lld ",dp[cnt][0]+dp[cnt][1]); 62 } 63 return 0; 64 } 65 /* 66 6 67 1 68 2 69 3 70 4 71 5 72 13 73 */