@Manish: Let b(n) = a(n) - 2. Then b(n) = b(n-1) + b(n-2) - b(n-5). We
can write this recurrence as a matrix multiplication as follows:
-- -- -- -- -- --
| b(n+1) | | 1 1 0 0 0 -1 | | b(n) |
| b(n) | | 1 0 0 0 0 0 | | b(n-1) |
| b(n-1) | | 0 1 0 0 0 0 | | b(n-2) |
| b(n-2) | = | 0 0 1 0 0 0 | x | b(n-3) |
| b(n-3) | | 0 0 0 1 0 0 | | b(n-4) |
| b(n-4) | | 0 0 0 0 1 0 | | b(n-5) |
-- -- -- -- -- --
Then
k
-- -- -- -- -- --
| b(n+k) | | 1 1 0 0 0 -1 | | b(n) |
| b(n+k-1) | | 1 0 0 0 0 0 | | b(n-1) |
| b(n+k-2) | | 0 1 0 0 0 0 | | b(n-2) |
| b(n+k-3) | = | 0 0 1 0 0 0 | x | b(n-3) |
| b(n+k-4) | | 0 0 0 1 0 0 | | b(n-4) |
| b(n+k-5) | | 0 0 0 0 1 0 | | b(n-5) |
-- -- -- -- -- --
so computing A^k = A to the kth power will do the trick. You can do
this in O(log(k)) operations.
Dave
On Jan 25, 9:23 am, manish patel <[email protected]> wrote:
> This is a question from spoj. can anyone tell me how to approach this
> problem.
>
> https://www.spoj.pl/problems/JZPCIR/
>
> Jumping Zippy likes to jump. He jumps every day and feels boring. Then he
> think of a new way to jump. He jumps on a big round plaza. The plaza is
> divided into n sectors numbered clockwise from 0 to n-1. Firstly, he stands
> on sector 0. Each time, when he is stand on sector x, he can jump to sector
> (x-2)%n, (x-1)%n, (x+1)%n or (x+2)%n. His goal is to jump to each sector
> exactly once and jump back to sector 0 at last. And for the first jump, he
> never jumps to sector n-1 or sector n-2. He wants to find the number of
> different ways in which he can complete his goal.
> Input
>
> First line is a number t, which is the number of testcases. (1<=t<=1000)
> The following t lines, each line contains a integer n, which is the number
> of sectors. (5<=n<=10^18)
>
> Then following t lines, each line contains a integer n, which is the number
> of sectors. (5<=n<=10^18)
>
> * *
> *Output*
>
> For each query n, output a line which contains one integer, the number of
> different ways Zippy can complete his goal in, modulo 10^9+9.
> Example
>
> *Input:*
> 5
> 5
> 6
> 7
> 8
> 9
>
> *Output:*
> 12
> 16
> 23
> 29
> 41
>
> PS- after googling i found this as:
>
> "Number of sequences of length n with elements {-2,-1,+1,+2}, counted up to
> simultaneous reversal and negation, such that the sum of elements of the
> whole sequence but of no proper subsequence equals 0 modulo n. For n>=4,
> the number of Hamiltonian (undirected) cycles on the circulant graph
> C_n(1,2)."
>
> And the recurrence is a(n)=a(n-1)+a(n-2)-a(n-5)-2
> --but i am sure this will give TLE. (n<=10^18)
> Can anyone tell how to solve this problem ...
>
> With Regards
>
> Manish Patel
> BTech
> Computer Science And Engineering
> National Institute of Technology -Allahabad
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
