# PROBLEM LINK:

# DIFFICULTY

SIMPLE

# PREREQUISITES

Simple Math, Repeated Squaring

# PROBLEM

How many sequences of 0s and 1s (0 meaning a hug, 1 meaning a kiss) of length N are possible, such that after the first 1 appears at index i, every **alternate** index after i - formally, i+2, i+4, i+6 and so on - is also 1. Note that this constraint is forced only by the first 1 and no subsequent 1s.

# QUICK EXPLANATION

Suppose the sequence was to start with a 0, then all possible sequences of length N-1 are valid.

Now, if the sequence were to start with a 1, then every odd index in the sequence (assuming the sequence is 1-based) will be 1; the rest of the **floor(N/2)** indices can be either 0 or 1, mutually exclusively.

Thus we get the formula

`f(N) = f(N-1) + 2`

^{floor(N/2)}

Since N can be as much as 10^{9} we cannot use this recursive formulation as it is.

The Explanation section below is about finding a closed form from the above recursive formula

# EXPLANATION

Seeing the floor function and division by 2 immediately gives us the insight that we should find the formula for odd and even N.

Let `f`

_{o}`(N)`

and `f`

_{e}`(N)`

be the functions that are defined for the odd and even values of N respectively. Thus,

`f(N) = if N is odd then f`

_{o}`(N) else f`

_{e}`(N)`

`(1) ... f`

_{o}`(N) = f`

_{e}`(N-1) + 2`

^{(N-1)/2}

`(2) ... f`

_{e}`(N) = f`

_{o}`(N-1) + 2`

^{N/2}

From `(1)`

and `(2)`

we can derive

`(3) ... f`

_{o}`(N) = f`

_{o}`(N-2) + 2`

^{(N-1)/2} `+ 2`

^{(N-1)/2}

`(4) ... f`

_{e}`(N) = f`

_{e}`(N-2) + 2`

^{N/2} `+ 2`

^{(N-2)/2}

Where,

`f`

_{o}`(1) = 2`

`f`

_{e}`(0) = 1`

These formulas are already very usable. We can use matrix exponentiation on `f`

_{o}`(N)`

or `f`

_{e}`(N)`

based on whether N is even or odd. But we can do a little better and find closed form formulas of `f`

_{o} and `f`

_{e}.

Let,

`t`

_{o}`(N)`

= `f`

_{o}`(N) - f`

_{o}`(N-2)`

= `2`

^{(N-1)/2} `+ 2`

^{(N-1)/2} = `2`

^{(N+1)/2}

`t`

_{o}`(3) = 2`

^{2}

`t`

_{o}`(5) = 2`

^{3}

`t`

_{o}`(7) = 2`

^{4}

`...`

`t`

_{o}`(N) = 2`

^{(N+1)/2}

Adding all of the above gives us,

`f`

_{o}`(N) - f`

_{o}`(1) =`

∑_{[n = 0 to (N+1)/2]} `2`

^{n} `- 2`

^{1} `- 2`

^{0}

`f`

_{o}`(N) - 2 = 2`

^{(N+1)/2 + 1} `- 1 - 2 - 1`

(summation of Geometric Progression)

`f`

_{o}`(N) = 2`

^{(N+1)/2 + 1} `- 2`

Similarly, we want to find the closed form for `f`

_{e}.

Let,

`t`

_{e}`(N)`

= `f`

_{e}`(N) - f`

_{e}`(N-2)`

= `2`

^{N/2} `+ 2`

^{N/2 - 1}

`t`

_{e}`(2) = 2`

^{1} `+ 2`

^{0}

`t`

_{e}`(4) = 2`

^{2} `+ 2`

^{1}

`t`

_{e}`(6) = 2`

^{3} `+ 2`

^{2}

`...`

`t`

_{e}`(N) = 2`

^{N/2} `+ 2`

^{N/2 - 1}

Adding all of the above gives us,

`f`

_{e}`(N) - f`

_{e}`(0) =`

∑_{[n = 0 to N/2]} `2`

^{n} `- 2`

^{0} + ∑_{[n = 0 to (N/2 - 1)]} `2`

^{n}

`f`

_{e}`(N) - 1 = 2`

^{N/2 + 1} `- 1 - 1 + 2`

^{N/2} `- 1`

(summation of Geometric Progression)

`f`

_{e}`(N) = 2`

^{N/2 + 1} `+ 2`

^{N/2} `- 2`

Thus we can find the value of `f(N)`

from the following two expressions

`f(N) = 2`

^{(N+1)/2 + 1} `- 2`

, for odd N

`f(N) = 2`

^{N/2 + 1} `+ 2`

^{N/2} `- 2`

, for even N

To further simplify the formula, you can rewrite the expressions for odd and even N as follows,

`f(N) = 2`

^{(N+1)/2} `+ 2`

^{(N+1)/2} `- 2`

, for odd N

`f(N) = 2`

^{N/2 + 1} `+ 2`

^{N/2} `- 2`

, for even N

Or,

`f(N) = 2`

^{ceil((N+1)/2)} `+ 2`

^{floor((N+1)/2)} `- 2`

, for any N

The value of `2`

^{n} can be found by repeated squaring.

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here