Round 1 D - Well-known Numbers CodeForces - 225B-K阶斐波那契数列

75 阅读 0 评论 50 点赞

我是靠谱客的博主烂漫春天，最近开发中收集的这篇文章主要介绍Round 1 D - Well-known Numbers CodeForces - 225B-K阶斐波那契数列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接:
https://vjudge.net/contest/168327#problem/D

Numbers k-bonacci (k is integer, k > 1) are a generalization of Fibonacci numbers and are determined as follows:

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.

You’ve got a number s, represent it as a sum of several (at least two) distinct k-bonacci numbers.

Input
The first line contains two integers s and k (1 ≤ s, k ≤ 109; k > 1).

Output
In the first line print an integer m (m ≥ 2) that shows how many numbers are in the found representation. In the second line print m distinct integers a1, a2, …, am. Each printed integer should be a k-bonacci number. The sum of printed integers must equal s.

It is guaranteed that the answer exists. If there are several possible answers, print any of them.

Example
Input
5 2
Output
3
0 2 3
Input
21 5
Output
3
4 1 16

大意：
K阶斐波那契数列，给出数字 s ，求这个数列中的数字和为 s 的。（假设必定存在）

思路：
构造出这个数列，然后从后往前找即可。找到一个用 s 减去，直到 s 为 0。

#include<bits/stdc++.h>
#define mem(s,t) memset(s,t,sizeof(s))
typedef long long ll;
using namespace std;
//#define LOCAL
int k,s;
const int MAXN =1e6+10;
int F[MAXN];
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
mem(F,0);
cin>>s>>k;
int sum=1,m=0,t=1;
F[1]=1;
for(int i=2;;i++){
F[i]=sum;
if(sum>s) break;
sum+=F[i];
if(i>k) m=F[i-k];
sum-=m;
t++;
}
//for(int i=1;i<=t;i++) cout<<F[i]<<" "<<endl;
//cout<<1<<endl;
vector<int> ans;
while(s){
int cnt=upper_bound(F+1,F+t+1,s)-F;
cnt--;
s-=F[cnt];
ans.push_back(F[cnt]);
}
printf("%dn",ans.size()+1);
int flag=1;
printf("0 ");
for(int i=0;i<ans.size();i++){
if(flag) flag=0;
else printf(" ");
printf("%d",ans[i]);
}
puts("");
return 0;
}