Energizer Knight

时间限制: 1 Sec  内存限制: 128 MB

题目描述

As previously discussed in the ab Knight problem, a knight is the only piece that can “jump” over pieces. Namely, a typical knight can move 1 square up, down, left or right, followed by 2 squares in a perpendicular direction. Thus, if a knight is at square (x, y), after its jump it can end up at one of these eight positions: (x ± 1, y ± 2), (x ± 2, y ± 1), provided that they are in bounds and there isn’t a piece on the destination square.

An Energizer Knight can make many, many jumps!!! Consider a single knight starting at square (x1 , y1 ) and making exactly k jumps to end up at the target square (x2 , y2 ). Naturally since the knight wants to jump around a lot it’s allowed to hit the same square multiple times, even the starting square and the target square. The only thing that matters is that it ends up at the target square after precisely k consecutive jumps. In a sequence of consecutive jumps, the ending square of the previous jump is the starting square of the subsequent jump.
Typically,  there  are  many  paths  of  length  k  between  any  two  squares  on  a  standard  8×8 chessboard. For this question, you are asked how many different paths of k consecutive jumps there  are  between  two  squares  (x1 ,  y1 )  and  (x2 ,  y2 ).  Since  the  answer  to  the  query  can  been exceedingly large, you are to give your answer modulo 10007. We model a path as a sequence of  locations a0 , a1 , a2 , … ak , where each ai  is a location on a standard chess board, a0  = (x1 , y1 ),  ak  = (x2 , y2 ), and for each i, 0 ≤ i < k, a_i  → a_i+1  represents a valid jump by a knight. Two paths (a0 , a1 , a2 , … ak ), and (b0 , b1 , b2 , … bk ) are considered different if there exists an i such that 0 ≤ i ≤ k, where ai  ≠ bi .
The Problem
Given the starting square of a knight (x1 , y1 ), a target square for a knight (x2 , y2 ) and a number of  consecutive jumps to perform, calculate the number of different paths the knight could take modulo 10007.

输入

The first line of input will contain a single positive integer, n (n ≤ 20), representing the number of input cases to process. The input cases follow, each on one line. Each case consists of five space separated integers: x1  (1 ≤ x1  ≤ 8), y1  (1 ≤ y1  ≤ 8), x2  (1 ≤ x2  ≤ 8),  y2  (1 ≤ y2  ≤ 8), and k (1 ≤ k ≤ 10¹⁸ ).

输出

For each case, output a single line with a single integer representing the number of paths of exactly k jumps between the starting and ending squares modulo 10007

样例输入

 

样例输出

 

题解

题目大意为一个国际象棋中的骑士在棋盘上瞎跳，求从(x1, y1)跳到(x2, y2)步长为k的路径的数量。

预处理：dp[x1][y1][x2][y2][i]为从(x1, y1)跳到(x2, y2)步长为\(2^i\)的路径的数量。

f[x][y][k]表示骑士从起始点k步跳到(x, y)的方案数。k最大为\(10^{18}\)，是个极大的数，数组无法开这么大。这时预处理就有用了。对于k，可以将其表示成二进制形式，比如说k可以表示成\(2^{i_1}+2^{i_2}+..+2^{i_m}\)的形式。我们就可以通过预处理的dp数组将f从0步的状态一步步转移到\(2^{i_1}+2^{i_2}+...+2^{i_m}\)（也就是k）的状态。我们用另一个数组g[x][y]记录上一个状态，当g记录的为跳了\(2^{i_1}+2^{i_2}+...+2^{i_{m-1}}\)步的状态时，向跳\(2^{i_1}+2^{i_2}+...+2^{i_m}\)步状态的转移为: f[x2][y2] += g[x1][y1] * dp[x1][y1][x2][y2][m]。

代码