题解:
首先我们用Fib贪心的找出一组解.
假如我们利用二进制存储得到的那组解.
例如15=13+2
就是(从小到大)010001,分别代表1,2,3,5,8,13.
由于我们知道由于Fib数列的性质,001等价于110.
所以我们需要知道找到的那组解一共能够变换出多少方案.
我们依次考虑得到的那组解中的每个1,令$f[i][0]$表示第$i$个一在变换后的方案中是$0$的方案数,$f[i][1]$同理.
我们首先观察001变换出110的性质,我们不难发现只能变换出这样的形式:
1->110->11010
即如果有$k$个空位,则有$\lfloor\frac{k}{2}\rfloor$种方案,知道了这些就不难dp了.
详情见代码.
代码:
#include<cstdio> #include<cctype> #include<cstring> #include<climits> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; ll f[90][2]; ll fib[90]; int ins[90],cnt; int main(){ ll n; cin>>n; int i,j; for(fib[1]=1,fib[2]=2,i=3;i<=88;++i) fib[i]=fib[i-1]+fib[i-2]; for(i=88;i>=1;--i) if(n>=fib[i]) n-=fib[ins[++cnt]=i]; f[cnt][1]=1; f[cnt][0]=(ins[cnt]-1)>>1; for(i=cnt-1;i>=1;--i){ f[i][1]=f[i+1][0]+f[i+1][1]; f[i][0]=f[i+1][0]*((ins[i]-ins[i+1])>>1)+f[i+1][1]*((ins[i]-ins[i+1]-1)>>1); } cout<<f[1][0]+f[1][1]<<endl; return 0; }