cf 126D - Fibonacci Decomposition

题目大意

\(t\le 10^5\)组询问

每次询问\(1\le n\le 10^{18}\)

求有多少种\(n\)的\(fibonacci\)分解

分解定义为：每个\(fib\)数最多选一个，且和为\(n\)

分解出来的数是无序的

分析

妙不可言

可以先将\(n\)分解无相邻\(1\)的\(fib\)码

对于每个\(1\)，可以拆分成\(1\)，\(011\)，\(01011\)，\(0101011\)，\(\cdots\)(最高位对齐)

然后再通过\(dp\)求解答案

单词复杂度为\(O(\log)\)

做法

先生成前\(90\)个\(fib\)

对于每个\(n\)，将\(fib\)从大到小枚举，求出\(n\)的无相邻\(1\)的\(fib\) 码

那么求出每个\(1\)有多少种可能的拆法，就可以通过乘法原理求出答案

可能的拆法数依赖于相邻两个\(1\)之间的间隔

从右往左dp

dp[i][1]表示这一位不分解的方案数

dp[i][0]表示这一位分解了（留出一个0的空位）的方案数

那么就有

\(dp[i][1]=dp[i+1][0]+dp[i+1][1]\)

\(dp[i][0]=dp[i+1][0]*\lfloor(ps[i]-ps[i+1])/2\rfloor+dp[i+1][1]*\lfloor(ps[i]-ps[i+1]-1)/2\rfloor\)

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

inline int ri(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

inline LL rl(){

	LL x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int m;

LL n;

LL fib[93];

int ps[93],tt;

int dp[93][2];

LL getans(LL n){

	int i;

	for(tt=0,i=90;i>0;--i) if(n>=fib[i]){

		n-=fib[i];

		ps[++tt]=i;

	}

	ps[++tt]=0;

	dp[tt][1]=1; dp[tt][0]=0;

	for(i=tt-1;i>0;--i){

		dp[i][0]= dp[i+1][1]*((ps[i]-ps[i+1]-1)/2) + dp[i+1][0]*((ps[i]-ps[i+1])/2);

		dp[i][1]= dp[i+1][0] + dp[i+1][1];

	}

	return dp[1][0]+dp[1][1];

}

int main(){

	int i;

	for(fib[0]=fib[1]=1,i=2;i<=90;i++) fib[i]=fib[i-1]+fib[i-2];

	m=ri();

	while(m--){

		n=rl();

		printf("%I64d\n",getans(n));

	}

	return 0;

}

巴特西

cf 126D - Fibonacci Decomposition

题目大意

分析

做法

solution

最新文章

热门文章