Codeforces225B - Well-known Numbers

Description

定义\(k\)-bonacci数列\(\{F_n\}\)：\(F_i=0 \ (i<k),F_i=1 \ (i=k),F_i=\sum_{j=i-k}^{i-1}F_j\)

给出\(s(s\leq10^9)\)和\(k(k\leq10^9)\)，将\(s\)拆成若干个\(k\)-bonacci数之和。

Solution

结论：重复从\(s\)中减掉最大的\(F_i\)，一定能使\(s=0\)。

可以用数学归纳法证明。

若对于正整数\(k\)，\(\forall s\in [0,F_k-1]\)该结论成立，则\(\forall s\in [F_k,F_{k+1}-1]\)，其下最大的\(F_i\)为\(F_k\)，而\(s-F_k\in [0,F_{k-1}-1]\)，其必然也能按上述方法减至0。

而因为\(k=1\)时该结论成立，所以\(\forall s\)该结论均成立。

Code

//Well-known Numbers

#include <cstdio>

#include <algorithm>

using namespace std;

int const N=1e5+10;

long long f[N];

int n,m,ans[N];

int main()

{

    int s,k; scanf("%d%d",&s,&k);

    int n; f[1]=1;

    for(n=2;f[n-1]<s;n++)

        for(int j=max(1,n-k);j<=n-1;j++) f[n]+=f[j];

    int m=0;

    for(int i=n-1;i>=1&&s;i--) if(f[i]<=s) ans[++m]=f[i],s-=f[i];

    if(m<2) ans[++m]=0;

    printf("%d\n",m);

    for(int i=1;i<=m;i++) printf("%d ",ans[i]);

    puts("");

    return 0;

}

P.S.

看标签猜结论系列binary search greedy number theory。不过根本不需要binary search啊！

巴特西

Codeforces225B - Well-known Numbers

Description

Solution

Code

P.S.

最新文章

热门文章