1513. Lemon Tale

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<queue>

#include<stack>

#include<cmath>

#define LL long long



using namespace std;

const int N=10005;

const int M=1500;

const int K=10000;

struct node

{

    short int a[M];

    int I;

}ans[N];

void equ(int l1,int l2)

{

    ans[l1].I=ans[l2].I;

    for(int i=ans[l1].I-1;i>=0;--i)

    ans[l1].a[i]=ans[l2].a[i];

}

void add(int l1,int l2)

{

    int k=max(ans[l1].I,ans[l2].I);

    for(int i=0;i<k;++i)

    {

        ans[l1].a[i]+=(ans[l2].a[i]);

        if(ans[l1].a[i]>=K)

        {ans[l1].a[i]-=K;++ans[l1].a[i+1];}

    }

    if(ans[l1].a[k]>0)

    ++k;

    ans[l1].I=k;

}

void sub(int l1,int l2)

{

    int k=ans[l1].I;

    for(int i=0;i<k;++i)

    {

        ans[l1].a[i]-=(ans[l2].a[i]);

        if(ans[l1].a[i]<0)

        {ans[l1].a[i]+=K;--ans[l1].a[i+1];}

    }

    while(ans[l1].a[k-1]==0)

    --k;

    ans[l1].I=k;

}

void print(int x)

{

    for(int i=ans[x].I-1;i>=0;--i)

    {

        int k=ans[x].a[i];

        if(i<ans[x].I-1)

        for(int j=0;j<4;++j)

        {

            if(k==0)

            printf("0");

            else

            k=k/10;

        }

        if(ans[x].a[i])

        printf("%d",ans[x].a[i]);

    }

    printf("\n");

}

int main()

{

    //freopen("data","r",stdin);

    int n,m;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        int k=n+1;

        for(int i=0;i<=n+1;++i)

        {

            ans[i].I=0;

            for(int j=0;j<M;++j)

            ans[i].a[j]=0;

        }

        ans[0].a[0]=1;

        ans[0].I=1;

        equ(k,0);

        for(int i=1;i<=n;++i)

        {

            equ(i,k);

            add(k,i);

            if(i-m-1>=0)

            sub(k,i-m-1);

        }

        print(k);

    }

    return 0;

}