BZOJ2660: [Beijing wc2012]最多的方案

题解:

首先我们用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;
}