How we can find large Pell Number and its modulus in efficient way?
Problem 4: The Price of Death
Robert Baratheon, King of the Seven Kingdoms, is very insecure. He had led the rebellion which smashed the might of the previous king, Aerys (II) Targaryen (the Mad King). After the Mad King’s death, his wife gave birth to Daenerys who was then smuggled across the narrow sea to Pentos. Robert has now come to know of her existence and seeing that she holds a better claim to the Iron Throne, conspires to assassinate her. He thinks of hiring a Faceless Man to do the job. Little does he know of the price he would have to pay.
The Faceless Man assures that the execution will be a success but provides no definite time guarantees. For the nth minute he spends in Robert’s service, his price in silver coins is the sum of: the number of silver coins he earned the previous minute, twice those he earned two minutes before, thrice those he earned three minutes before and (once) those he earned four minutes before. For the first four minutes, his prices are 1, 2, 5 and 12 coins; the cost for the fifth minute is hence, 29. As payment he asks for the silver coins he earned in the Nth minute, where N is the number of minutes he is in Robert’s service. Since Robert does not know how much time the Faceless Man will take, he decides to find the cost for some values of N. Given this value, find the cost of the assassination modulo 10^9 + 7. Input :
First line an integer Q number of queries . Each of the following Q lines contains a integer N. Output :
For each query output an Integer which denote cost of assassination for Nth minute modulo 10^9 + 7 . Constratints :
1 <= Q <= 52000 1 <= N <= 10^18 Sample Input :
5
1
2
5
100
1000
Sample Output:
1
2
29
852799803
671754329
This is very similar to finding the Nth Fibonacci number in O(log N) time. You should read the tutorial about linear recurrences here:
http://community.topcoder.com/tc?module=Static&d1=features&d2=010408
We're looking for A[N], where A satisfies the identity A[i]=A[i-1]+2A[i-2]+3A[i-3]+A[i-4].
Construct a matrix P representing the recurrence and another one S representing the last 4 values of A. One suitable pair is:
0th row of P: 1 2 3 1 (the coefficients of the recurrence)
P[i][i-1]=1 for 0 < i < 4; all other values of P are 0
0th column of S: A[i], A[i-1], A[i-2], A[i-3] for some suitable i (like i=4 which you know the values of); all other columns of S contain zeroes only
Now, notice that the product P x S gives the matrix S for i+1 (first column: A[i+1], A[i], A[i-1], A[i-2]; all the other values are zeroes). So all you need to do is repeat the multiplication N-4 times, and you get "S for N" from "S for 4".
Except for commutativity, matrix multiplication works pretty much in the same way as multiplication of integers, so you can first compute P to power N-4. This can be done in O(lg(N)) time (since the matrix has constant size), in the same way as raising integers to high powers. Then, just multiply the result from the right by S, e.g. if R=P^(N-4), then compute R x S, and the upper left value of the resulting matrix is the number you're looking for.