题目信息
题目来源：Codeforces Round #139 (Div. 2)；
在线评测地址：CF#225B；
运行限制：(2.00 extrm{s}/256 extrm{MiB})。
题目描述
Numbers (k)-bonacci ((k) is integer, (k > 1)) are a generalization of Fibonacci numbers and are determined as follows:
定义 (k) 阶斐波那契数列如下：
- (F(k, n) = 0), for integer (n), (1 ≤ n < k);
- (F(k, k) = 1);
- (F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k)), for integer (n), (n > k).
Note that we determine the k-bonacci numbers, F(k, n), only for integer values of n and k.
(F(k,n)) 只对整数定义（或者严格来说是正整数）。
You've got a number (s), represent it as a sum of several (at least two) distinct (k)-bonacci numbers.
你得到了一个数 (s)，试用若干个互异的 (k) 阶斐波那契数的和表示。数据保证存在解。
输入格式
一行，(s) 和 (t)。
输出格式
第一行一个正整数 (m)，表示所用来表示和的数的个数。
下一行 (m) 个正整数，表示数。每个数都应该是 (k) 阶斐波那契数，且和为 (s)。
数据规模与约定
(1le s,kle 10^9)，(k>1)。
分析
给出一个数列的定义，要求用这个数列的某些互异的项之和来表示某个数。
首先，注意到这个数列的定义，以及这个数列是单调的，我们不妨考虑一下贪心。即：自后往前选，选到可以选进去的就选进去。
对于这个做法，我们要考虑这么几个问题：
- 这个做法是否一定存在可行解？
- 这个做法能否满足互异和至少两个的要求？
首先是可行性的问题。根据事后诸葛亮可以推断确实是可行的。我们可以先证明几个引理：
( exttt{Lemma 1})：(F(k,n+1)le 2F(k,n))。
由定义显然可证。
( exttt{Lemma 2})：(F(k,k+t)=2^{t-1}(1le tle k))。
根据定义，简单推导可得。
( exttt{Theorem})：对于任意 (s,k)，使用贪心算法总有解。
- 当 (1le s<2^k) 时，根据 ( exttt{Lemma 2}) 可得一定有解；
- 当 (sge 2^k) 时，不妨设 (F(k,s^prime) le s<F(k,s^prime+1))，此时利用贪心算法得到的下一步必然是 (s-F(k,s^prime))。
根据 ( exttt{Lemma 1})，(s-F(k,s^prime)<F(k,s^prime+1)-F(k,s^prime)le F(k,s^prime))，即可以不使用 (F(k,s^prime))（或更大）来表示 (s-F(k,s^prime))。
综上，根据数学归纳法得证。
接下来就是一些有的没的的构造了。
对于互异而言是肯定不可能的，由定义易得。然而我们并不保证只有一个数的情况。
这个时候，我们可以加一个 (0)，这样就能水过去了（迫真）。
注意事项
- 注意是否对一个元素的情况特判；
- 注意是否有特殊处理前 (k) 个元素，同时注意元素的值域边界。
Code
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> vt, ans;
int main()
{
int s, k;
ll t = 1;
scanf("%d%d", &s, &k);
vt.push_back(1);
for (int i = 1; i < k && t <= s; i++, t <<= 1) // 特殊处理前 k 项，注意每一项都 <= s
vt.push_back(t);
while (true)
{
t = 0;
for (int j = 0; j < k && j < vt.size(); j++) // 用定义推后面的项
t += vt[vt.size()-j-1];
if (t > s) // 利用单调性
break;
vt.push_back(t);
}
for (int i = vt.size() - 1; i >= 0; i--) // 贪心
if (vt[i] <= s)
{
s -= vt[i];
ans.push_back(vt[i]);
}
if (ans.size() > 1)
{
printf("%d
", ans.size());
for (int i = 0; i < ans.size(); i++)
printf("%lld ", ans[i]);
}
else
printf("2
%lld 0
", ans[0]); // 大小等于 0 时特判
return 0; // 然后就 AC 了、
}