@Dave: Can you tell us how you got there from the problem description?

On Jan 25, 11:02 am, Dave <dave_and_da...@juno.com> wrote:
> @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 <manispatel...@gmail.com> 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- Hide quoted text -
>
> - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Reply via email to