[原创]SPOJ - VECTAR1 Matrices with XOR property [FWT]【数学】

2017-07-05 12:32:49 Tabris_ 阅读数：312

https://blog.csdn.net/qq_33184171/article/details/74408116

——————————————————————————————————————————
VECTAR1 - Matrices with XOR property
no tags

Imagine A is a NxM matrix with two basic properties1) Each element in the matrix is distinct and lies in the range of 1<=A[i][j]<=(NM)2) For any two cells of the matrix, (i1,j1) and (i2,j2), if (i1^j1) > (i2^j2) then A[i1][j1] > A[i2][j2] ,where 1 ≤ i1,i2 ≤ N1 ≤ j1,j2 ≤ M.Given N and M , you have to calculatethe total number of matrices of size N x M which have both the propertiesmentioned above. Input format:First line contains T, the number of test cases. 2T lines follow with N on the first line and M on the second, representing the number of rows and columns respectively.Output format:Output the total number of such matrices of size N x M. Since, this answer can be large, output it modulo 10^9+7Constraints:1 ≤ N,M,T ≤ 1000SAMPLE INPUT 122SAMPLE OUTPUT 4ExplanationThe four possible matrices are:[1 3] | [2 3] | [1 4] | [2 4][4 2] | [4 1] | [3 2] | [3 1]
Imagine A is a NxM matrix with two basic properties

1. Each element in the matrix is distinct and lies in the range of 1<=A[i][j]<=(N*M)

2. For any two cells of the matrix, (i1,j1) and (i2,j2), if (i1^j1) > (i2^j2) then A[i1][j1] > A[i2][j2] ,where

1 ≤ i1,i2 ≤ N

1 ≤ j1,j2 ≤ M.

^ is Bitwise XOR

Given N and M , you have to calculatethe total number of matrices of size N x M which have both the properties

mentioned above.

Input format:

First line contains T, the number of test cases. 2*T lines follow with N on the first line and M on the second, representing the number of rows and columns respectively.

Output format:

Output the total number of such matrices of size N x M. Since, this answer can be large, output it modulo 10^9+7

Constraints:

1 ≤ N,M,T ≤ 1000

SAMPLE INPUT

1

2

2

SAMPLE OUTPUT

4

Explanation

The four possible matrices are:

[1 3] | [2 3] | [1 4] | [2 4]

[4 2] | [4 1] | [3 2] | [3 1]

——————————————————————————————————————————

$if (i_1 \ xor\ j_1) > ( i_2 \ xor\ j_2 )\ \ \ then\ \ \ A[i_1][j_1] > A[i_2][j_2]$

$(i^j)$相同的这个集合内,任意排列即可,

a=(0,1,1,1,0,0,0,0,) 从第1个(第一个不是第0个)开始n个1
b=(0,1,1,1,0,0,0,0,) 从第1个开始m个1

$c[x]= \displaystyle \sum_{x=i\ xor\ j}a_i \times b_j$

——————————————————————————————————————————