KN2 - Travelling Knight 2
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 an integer T, the number of test cases. Each of the next T lines contains 2 integers : n, k.
Output T lines, one for each test case, containing the required total number of configurations. Since the answer can get very big, output it modulo 1000007.
Input: 3 2 1 2 2 3 3 Output: 1 5 7
1 <= T <= 50 2 <= n <= 24 1 <= k <= 10^9
In the input files, there will be two cases for each possible n. Constraints allows fast languages to get AC under 0.5s (total time for the 5 input files), with non-optimized scholar methods only. Advanced methods can be slightly faster, and needed to get AC with interpreted languages (without any guaranty for all of them). It is recommended to solve first the original problem TRKNIGHT in a very fast way. After that, solve this problem could remain a hard task ; it's not just a simple extension. Good luck and have fun ;-)
Edit(12/II/2017, compiler update) New TL.
It's quite a long way to get a desired solution...
Are you sure this problem can be solved using non-optimized scholar methods(I don' t count fft as such, just matrices)? I'm using cpp14 and I have a pretty optimized solution, it works in 0.02 in the easier version, however I'm getting TL.
Although I don't know whether my solution is an intended solution or not, I learned another fast computation technique. :)