Nice series of problems (Problem 109, 114, 115, 116, 117) to become familiar with linear recurrence. Turn dynamic programming into matrix exponentiation.

Constantly get timeouts.

Have a theoretical doubts:

If I use a function

int f(int x) {
    if (x <= 1) return 1;
    return f(x/2) + f(x/2 - 1);
}

what complexity there is?

I am trying to solve it in C. I used unsigned long long int but it still does not suffice beyond 33 . Might need a little hint or so as to where I am going wrong.

The logic is simple and is obv correct (not posting it here). But I need to work around the data type for larger integers.

I'm getting Wrong answers after everything I could possibly do. could anyone help me with that ?

Just for reason of testing, if n = 10^18 , answer is 417674472?