@Don: I got there from the recurrence in the last paragraph of Manish's posting.
Dave On Jan 25, 12:24 pm, Don <[email protected]> wrote: > @Dave: Can you tell us how you got there from the problem description? > > On Jan 25, 11:02 am, Dave <[email protected]> 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 <[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- 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 [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.
