Problem 1513 Timus

Lemon tale

 

- f[i]: numbers of binary strings s length i that have at most k consecutive 1

- Result: f[n]

- The ending of s may be:

0, 01, 011, 01..1 (k digits 1)

From this f[i] = f[i-1] + f[i-2] + + f[i-k-1]

Moreover, f[i] = f[i-1] + (f[i-2] + + f[i-k-1]) = 2* f[i-1] - f[i-k-2 ] // This is the formula we use!

- Should implement bigint

 

// 1513 Timus - Lemon tale

 

#include <iostream.h>

 

#define M 3011

#define NMAX 10005

 

class bigint

{

char a[M+1];

 

public:

bigint();

bigint operator - (bigint);

bigint operator * (int);

bigint operator = (int);

void print();

};

 

bigint::bigint()

{

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

a[i]=0;

}

 

bigint bigint::operator = (int x)

{

for (int i=M; i>0; i--)

{

a[i]=x % 10;

x/=10;

}

return *this;

}

 

bigint bigint::operator - (bigint x)

{

bigint b;

int c=0;

for (int i=M; i>0; i--)

{

b.a[i]=a[i]-x.a[i]-c;

if (b.a[i] < 0)

{

b.a[i]+=10;

c=1;

} else

c=0;

}

return b;

}

 

bigint bigint::operator * (int k)

{

bigint b;

int c=0;

for (int i=M; i>0; i--)

{

b.a[i]=a[i]*k+c;

c=b.a[i]/10;

b.a[i]%=10;

}

return b;

}

 

void bigint::print()

{

int i;

for (i=1; i<=M; i++)

if (a[i]!=0) break;

if (i<=M)

for (i=i; i<=M; i++)

cout << (int)a[i];

else

cout << 0;

}

 

int n, k;

bigint f[NMAX+1];

 

int main()

{

cin >> n >> k;

 

f[1]=1; // Note that the index is shifted by 2, so the result is f[n+2]

f[2]=1;

int i;

for (i=3; i<=n+2; i++)

{

f[i]=f[i-1]*2;

if (i>k+2)

f[i]=f[i]-f[i-k-2];

}

f[n+2].print();

 

return 0;

}