@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.
