Need help - BEAUTIFUL STONES 1

1

Could someone help me with the possible solution for the following question.
It is from a contest that ended today.
problem name:- BEAUTIFUL STONES 1
problem link:- https://www.hackerrank.com/contests/execute--19-1/challenges/beautiful-stones-1
problem:-
You have two different types of stones. Your task is to find the total number of different patterns that can be formed such that stone of same type appear in a blocks of odd length.

Input Format

The first line contains an integer T, representing the number of test cases.

Each of next T line contains an integer N, denoting the length of pattern

Note There are infinite supply of each stone

It is gaurenteed that N is even.

Constraints

1<=T<=100000

1<=N<=10^18

Output Format

For each test case print the total number of ways modulo 10^6+3 in a new line.

Sample Input 0

1 4

Sample Output 0

6

Explanation 0

6 Different ways are:

stone1 stone1 stone1 stone2

stone2 stone1 stone1 stone1

stone2 stone2 stone2 stone1

stone1 stone2 stone2 stone2

stone1 stone2 stone1 stone2

stone2 stone1 stone2 stone1

Ps:Thanks in advance

2

suppose f(x) denotes the number of ways to arrange the stones if we start with stone of type 1 always.

Now, for suppose we have the values for all x < i. So, f(i) = (f(i-1) + f(i-3) + f(i-5) + ....). as currently we can put only odd number of stones.

Note that this equation is similar to f(i) = f(i-1) + f(i-2) [as f(i-2) = f(i-3) + f(i-5) + f(i-7) + ..... ].

Now, we have considered that we are always starting with stone of type 1, so, we have to multiply the answer with 2 as we could have start with type 2 stone and just reversed the types of stones and we get another valid sequence.
Like suppose if one of the sequence is 1 2 1 1 1 we can reverse the types and we have another valid sequence : 2 1 2 2 2.

So, answer is just fibbonacci * 2.

3 Likes