Jacobsthal numbers

Jacobsthal numbers are analogous to fibonacci numbers

their series is 0 1 1 3 5 11 21 43 85…
Now I came across an interesting problem where i found use of this not so well-known series

if u want to know more abt this series LINK

The problem is :

PROBLEM STARTS HERE

The problem setter for this contest is also setting up problems for IHPC (in Techkriti).
There, he encountered a new field of writing parallel code and a totally new thinking style to go about solving algorithmic problems by doing computations in parallel.
He created the following problem:
He takes N processors numbered 1, 2, …, N. Each processors is initially given a number Ci and then all of them perform the following process in parallel:
First, each processor finds the sum of the numbers of the other N-1 processors.
After all processors are finished, each processor replaces its number with the sum it computed. To avoid very large numbers, the processors will keep track of their numbers modulo 98,765,431.
To make it more tough, he sets the processors to repeat this algorithm T times.
After thinking a bit more on the problem, he realised that this can also be solved very efficiently using sequential code instead. So, he decided to check if the Algorithmic community of IITK, the teams practicing for IOPC can solve it or not?

Constraints

1 ≤ N ≤ 50,000

0 ≤ Ci < 90,000,000

1 ≤ T ≤ 109

Input

Each input file consists of a single test case. Line 1 contains two space-separated integers, N and T.

From Lines 2 … N+1, line i+1 contains a single integer Ci.

Output
N lines, where line i contains a single integer representing the number computed by processor i
(modulo 98,765,431) at the end of the T iterations of the algorithm.

Sample Input

3 4

1

0

4

Sample Output

26

25

29

PROBLEM ENDS

Now i tried it solving using an example and derived a formula (I’m sure it’s correct)

after t iterations the elements of the array will be : jt(S) + (-1)^t(a)*

here jt -> 't’th jacobsthal number

a -> that particular element of array

S -> sum of all elements of array

Now that everything is set and i wrote code which produces jacobsthal numbers in linear time
that’s giving me TLE :frowning:
so please help me to find jacobsthal numbers in O(logn) time ( just like fibonacci numbers )

Thank You

1 Like

From your quote just like fibonacci numbers I assume you know how to generate fibonacci numbers in O(log N) complexity. Generating Jacobsthal Numbers is similar, just a small change in multiplying matrix:

|1 1|
|2 0|

Instead of

|1 1|
|1 0|

EDIT:

Link 1

Link 2

1 Like

Im new to the method in which we can generate fibonacci numbers in O(logn) time so can u please suggest me some tutorials or link where it is explained clearly :slight_smile: ( Explained from scratch ) :slight_smile:

perfect thanx :slight_smile:

Glad I could help :slight_smile:

@a1tiwari_ Could U please tell me the reason for the downvote for this answer??? It’s perfect and what wrong did u find in this answer!!

//