TRKNIGHT - Travelling Knight
Your task is simple. A knight is placed on the top left corner of a chessboard having 2n rows and 2n columns. In how many ways can it move such that it ends up at a corner after atmost K moves ?
The first line contains T the number of test cases. Each of the next T lines contain 2 integers : n,k
Output T lines, one for each test case, containing the required total number of configurations. Since the answers can get very big, output the answer modulo 1000007.
Sample Input :
Sample Output :
1 <= T <= 20
2 <= n <= 12
1 <= k <= 1000000000
|Added by:||Varun Jalan|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: NODEJS PERL 6 SCM chicken VB.net|
|Resource:||own problem used for Codechef Snackdown Onsite|
Python3 validator (by Francky) : OK ;-)
Hagen von Eitzen:
@ukasuevoli: don't forget the move sequence of length 0<k that simply stays in the initial corner
@varun ! How the answer for second case =5 ?
~ adieus ~:
need some hints ... should it be done with (A.M.)^K ?
Er, seems that it needs ~6 seconds on my PC for only one test case if multiplying 150 size matrices...
maybe you're right, it just seemed to me that it can be solved with fft...btw, multiplying 150 size matrices isn't enough?Last edit: 2010-01-30 11:05:19
yes, in fact I do not know how to do it using FFT :D
is that problem solvable without using FFT and such things(yes/no)? or that is the only way...