CF_225B _Well-known Numbers

50 阅读 0 评论 33 点赞

我是靠谱客的博主纯真河马，最近开发中收集的这篇文章主要介绍CF_225B _Well-known Numbers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 ≤ 10⁹; 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 mdistinct integers a₁, a₂, ..., a_m. 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.

题目背景是一个k—Fibonacci数列，也就是，第0，1项是1，然后后面的第i项为前面k项之和，即f[i]=f[i-1]+.....f[i-k],（i>=k+1），然后输入整数s，k，输出能使得加起来和为s的m（m>=2)个不同的k—Fibonacci数，1<=s<=10^9，k>1，考虑到k最小为2时，f[50]>=10^10，所以对于任意k，满足条件的整数不会超过10^9，只需要存储前50个就可以了。这样s依次减去小于它的最大Fibonacci值，直到s为0.

题目要求最少输出2个数，所以遇到恰好为Fibonacci数的s值，可以输出一个0。

代码：

 1 #include<stdio.h>
 2 #define max(a,b) ((a)>(b)?(a):(b))
 3 #define N 50
 4 typedef long long ll;
 5 ll f[N];
 6 int main(void)
 7 {
 8
int s,k;
 9
int i,j,ct=0;
10 
ll ans[N];
11
scanf("%d%d",&s,&k);
12
f[0]=f[1]=1;
13
f[2]=2;
14
for(i=3;i<N;i++)
15 
{
16
if(i>=k+1)
17
f[i]=2*f[i-1]-f[i-k-1];//i>=k+1,递推公式:f[i]=2*f[i-1]-f[i-k-1]
18
else for(j=i-1;j>=max(i-k,0);j--)
19
f[i]+=f[j];//否则f[i]为前面k项之和
20 
}
21
for(i=N-1;i>0;i--)
22 
{
23
if((s>=f[i]))
24 
{
25
s-=f[i];
26
ans[ct++]=f[i];
27 
}
28
if(s==0)
29 
{
30
if(ct==1){
31
printf("%dn",ct+1);
32
printf("0 ");
33 
}
34
else printf("%dn",ct);
35
for(i=0;i<ct;i++)
36
printf("%I64d%c",ans[i],i==ct-1?'n':' ');
37
return 0;
38 
}
39 
}
40
return 0;
41 }