@sudarshans the empty string is a valid string of length 0
@abhi92 Good catch 
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 