CROWD - Editorial

@sudarshans the empty string is a valid string of length 0

@abhi92 Good catch :slight_smile:

The partition into S only gives strings that have a 0 at the end.

Using arguments from the editorial one would be led to believe f(1) = 1.

But by setting f(1) = 2. We are ensuring that we calculate all the valid strings that end in 1.

1 Like

@author :
how can you say f[n] = f[n-1]+f[n-2]+f[n-3]
there f[0] = 0
f[1] = 0
f[2] = 0
f[3] = 1
then for n = 4 2^4 is 16 and f[4] = 1
then ans is ans = 2^4-1
ans = 15
am i right or not

can anyone explain the solution for test cases 5,6,7,8,9,10ā€¦i m not getting the logic behind itā€¦
it seems that this can be solved via normal mathematics but maybe i m getting it wrongā€¦
Thanks in advanceā€¦(y)

see http://fusharblog.com/solving-linear-recurrence-for-programming-contest/ to Matrix Exponentiation :smiley: