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