bzoj2660: [Beijing wc2012]最多的方案

这题意。。。注意不同的方案中不能有相同的斐波那契数中的相同指的是完全相同，就是一个不一样就行了

思维题

fib增长得很快，92就爆LL了

我们考虑用一个01串表示第几个斐波那契数是否选

对于一个合法的方案，可以通过令一个位的1变成0，再令下两位的0变成1的方式变成另一个方案

我们可以求出二进制最大的01串，然后不停消位

先得到一个p数组，表示那些位是1，这个是由大到小的

f[i][0/1]表示枚举到第i个位是1的位置，这个位置选不选

容易有f[i][1]=f[i+1][1]+f[i+1][0]

因为第i个斐波那契数只用前面的斐波那契数表示，总的方案数为(i-1)/2，所以

f[i][0]=f[i+1][1]*((p[i]-p[i+1]-1)/2)+f[i+1][0]*((p[i]-p[i+1])/2)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;

LL fib[110];int len,p[110];
LL f[110][2];
int main()
{
    fib[1]=1;fib[2]=2;
    for(int i=3;i<=90;i++)fib[i]=fib[i-1]+fib[i-2];
    LL n;
    scanf("%lld",&n);
    for(int i=90;i>=1;i--)
        if(n>=fib[i])n-=fib[i],p[++len]=i;
        
    f[len][0]=(p[len]-1)/2,f[len][1]=1;
    for(int i=len-1;i>=1;i--)
    {
        f[i][0]=f[i+1][1]*((p[i]-p[i+1]-1)/2)+f[i+1][0]*((p[i]-p[i+1])/2);
        f[i][1]=f[i+1][1]+f[i+1][0];
    }
    printf("%lld
",f[1][0]+f[1][1]);
    return 0;
}