自动搬运

查看原文

来自洛谷，原作者为

	我好蒻呀 **

搬运于2025-08-24 21:56:50，当前版本为作者最后更新于2018-02-06 22:21:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

• 这题出得真是妙。
• 首先我们可以证明，任意自然数都能被不相同的斐波那契数之和表示：

具体的可以参考：Zeckendorf's theorem

简单证明：

可以考虑归纳，显然对于 $n \leq 3$ 这个结论是成立的。

令 $f_k$ 表示斐波那契数列的第 $k$ 项，假设对于满足 $n < f_{k}$ 的自然数都能被不相同的斐波那契数表示，那么对于 $n=f_k$ 显然可以直接用 $f_k$ 表示。

对于满足 $f_k<n<f_{k+1}$ 的整数 $n$，因为 $n<f_{k+1}\leq 2f_{k}$，因此 $n-f_k<f_k$，所以 $n-f_k$ 的斐波那契数表示中肯定不包含 $f_k$，我们可以考虑用 $n-f_k$ 的斐波那契数表示加上 $f_k$，从而得到 $n$ 的斐波那契数表示。

• 而斐波拉契数列的递推公式 $f[i]=f[i-1]+f[i-2](i>2)$告诉我们了一个性质：数列中的任何一项（非第一第二项）能且只能分解为前两项之和，也只有相邻两项能够合并成下一项。
• 于是我们先倒过来想，将方案中所有能合并的不断合并，得到一个没有相邻两项的方案，而这个方案显然可以通过贪心，不断从大往小取得到。
• 我们将这个贪心得到的数列中第 $i$ 个数在斐波拉契数列中的编号记为 $pos[i]$，将这个方案所用元素个数记为 $cnt$。
• 则 $n=\sum \limits_{i=1}^{cnt}f[pos[i]]$。
• 根据前面的分解方式和得到的结论，我们能且只能找到一个这样不相邻的表示法（可以形象地理解，一种不相邻方案与另一种不相邻方案之间，其中一种的最大值比另一种的所有元素和还要来得大）。
• 接下来我们又反过来想，尝试在这个方案的基础上分解。
• 显然直接做是不可能的。
• 我们前面发现不相邻表示法是唯一的，这样我们可以考虑分阶段分解，想到DP。
• 令 $g[i][0/1]$ 表示将 $1...i$ 的元素进行变换后，恰好组成 $\sum \limits_{j=1}^{i}f[pos[j]]$ 的方案数，第二维的 $0/1$ 表示是/否分解第 $i$ 个元素，且第 $i$ 个阶段必须组成 $f[pos[i]]$，的方案数。
• 首先明确，若不分解第 $i$ 个元素，则 $(pos[i-1],pos[i])$ 的元素都不用，下一阶段只能用 $(pos[i],pos[i+1]])$ 的元素分解。
• 否则若分解第 $i$ 个元素，则用到 $(pos[i-1],pos[i])$ 或 $[pos[i-1],pos[i])$ 的元素（取决于 $i-1$ 有没用上），下一阶段就能用 $[pos[i],pos[i+1]])$ 的元素分解。
• 而分解一个元素，需要它前两项的和，若这个和还能分解，则分解的必须是前一项。由此得到，分解一次需要两项是空出来的。
• 于是转移方程显然：

$g[i][1]=g[i-1][1]+g[i-1][0]$ $g[i][0]=g[i-1][1]*((pos[i]-pos[i-1]-1)\ div\ 2)+g[i-1][0]*((pos[i]-pos[i-1])\ div\ 2)$

• 初值也显然：$g[1][1]=1,\ g[1][0]=(pos[1]-1)\ div\ 2$

代码：

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll; 

const int MaxN = 110; 

ll n, f[MaxN]; 
int m, cnt, pos[MaxN]; 
int g[MaxN][2]; 

int main()
{
	std::cin >> n; 
	f[1] = 1, f[2] = 2; 
	for (m = 3; f[m - 1] <= n; ++m)
		f[m] = f[m - 1] + f[m - 2]; 
	--m; 
	for (int i = m; i >= 1; --i)
		if (n >= f[i])
		{
			n -= f[i]; 
			pos[++cnt] = i; 
		}
	std::sort(pos + 1, pos + cnt + 1); 
	g[1][1] = 1, g[1][0] = pos[1] - 1 >> 1; 
	for (int i = 2; i <= cnt; ++i)
	{
		g[i][1] = g[i - 1][0] + g[i - 1][1]; 
		g[i][0] = g[i - 1][1] * (pos[i] - pos[i - 1] - 1 >> 1) + g[i - 1][0] * (pos[i] - pos[i - 1] >> 1);  
	}
	
	printf("%d\n", g[cnt][0] + g[cnt][1]);  
	
	return 0; 
}