B. Well-known Numbers（数学构造 + 贪心）

107 阅读 0 评论 71 点赞

我是靠谱客的博主雪白香水，最近开发中收集的这篇文章主要介绍B. 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 ≤ 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.

Examples

input

Copy

5 2

output

Copy

3
0 2 3

input

Copy

21 5

output

Copy

3
4 1 16

这题首先给出递推式

F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k),

然后 F(k, n-1) = F(k, n - 2) + F(k, n - 3) + ... + F(k, n - k-1),

错位相减得 F(k, n) - F(k, n-1) = F(k, n-1) - F(k, n - k-1).

即 F(k, n ) = 2*F(k, n - 1) -F(k, n - k-1)

根据递推式预处理数列，值的一提的是让找到几个数之和 = s,分、故求到 > s的数跳出即可

然后贪心，真不好想

结论：重复从s中减掉最大的Fi，一定能使s=0。不是很清楚为什么就可以这样

AC Code：

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<bitset>
#include<cctype>
#define LL long long
#define maxn (LL)1e5
#define INF 0x3f3f3f3f
const double eps = 0.0000001;
using namespace std;
inline int sgn(double x) {
    return (x > eps) - (x < -eps);
}
#define re register
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(S==T) return EOF;}
    return *S++;
}
inline int read()
{
	re int x=0,f=1;re char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
LL f[maxn];
int  main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    #endif // ONLINE_JUDGE
    LL n  = 3;
    f[1] = 1;
    f[2] = 1;
    LL s,k;
    cin>>s>>k;
    for(;f[n-1]<s;++n)//递推预处理
    {
        f[n] = 2*f[n-1] - (n-k-1<0?0:f[n-k-1]);
        //cout<<f[n]<<endl;
    }
   // return 0;
    vector<int> v;
    n;
    while(s)//贪心
    {
        if(s>=f[n]) {
            s = s -  f[n];
            v.push_back(f[n]);
        }
        n--;
    }
    if(v.size()<2) v.push_back(0);
    cout<<v.size()<<endl;
    for(int i =0;i<v.size();++i)
        cout<<v[i]<<" ";




}

其实当时没想到贪心的话可以dfs遍历一遍，因为题目说一定有解。还要读清输出要求，不能有重复的，所以可以倒序遍历。

其实正序倒序都试一下至少一个可A，这才是精髓！

AC Code:

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<bitset>
#include<cctype>
#define LL long long
#define maxn (LL)1e5
#define INF 0x3f3f3f3f
const double eps = 0.0000001;
using namespace std;
inline int sgn(double x) {
    return (x > eps) - (x < -eps);
}
#define re register
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(S==T) return EOF;}
    return *S++;
}
inline int read()
{
	re int x=0,f=1;re char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
LL f[maxn];
LL num[maxn];
LL Idx;
bool  flag = 1;
void sum(LL Sum,LL idx,LL IDX)
{
    if(Sum<0) return ;
    if(idx<=0) return ;

    if(Sum==0) {
            Idx  = IDX;
            flag = 0;
        return ;
    }
    if(flag == 0) return ;

    num[IDX] = f[idx];//先选后不选，记住这种顺序，省去许多麻烦
    sum(Sum - f[idx],idx-1,IDX+1);

    sum(Sum,idx-1,IDX);


}
int  main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    #endif // ONLINE_JUDGE
    LL n  = 3;
    f[1] = 1;
    f[2] = 1;
    LL s,k;
    cin>>s>>k;
    for(;f[n-1]<s;++n)//递推预处理
    {
        f[n] = 2*f[n-1] - (n-k-1<0?0:f[n-k-1]);
        //cout<<f[n]<<endl;
    }
   sum(s,n,1);
   cout<<Idx-1<<endl;
   if(Idx-1==1){
    cout<<0<<" ";
   }
   for(int i = 1;i<Idx;++i)
    cout<<num[i]<<" ";




}