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

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


博客爬取于2020-06-14 22:39:46
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/74408116


题目链接:http://www.spoj.com/problems/VECTAR1/
——————————————————————————————————————————
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(i1 xor j1)>(i2 xor j2)   then   A[i1][j1]>A[i2][j2]if (i_1 \ xor\ j_1) > ( i_2 \ xor\ j_2 )\ \ \ then\ \ \ A[i_1][j_1] > A[i_2][j_2]


显然按照a[i][j]a[i][j]升序排列后对应的(ij)(i^j)也是升序

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

所以问题就是找(ij)(i^j)相同的个数,

很容易想到FWT,
构造两个向量a,b
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

然后进行FWT即可

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

上式即是期望结果,

计算全排列的时候预处理下就能做到O(1)计算

总复杂度O(T×1024×log(1024))O(T\times 1024\times \log{(1024)})

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
int n,m,len,a[2222],b[2222];

void FWT(int a[],int n){
for(int d=1;d<n;d<<=1)
for(int m=d<<1,i=0;i<n;i+=m)
for(int j=0;j<d;j++){
int x=a[i+j],y=a[i+j+d];
a[i+j]=(x+y)%MOD,a[i+j+d]=(x-y+MOD)%MOD;
//xor:a[i+j]=x+y,a[i+j+d]=(x-y+MOD)%MOD;
//and:a[i+j]=x+y;
//or :a[i+j+d]=x+y;
}
}

void UFWT(int a[],int n){
const int rev = (MOD+1)>>1;
for(int d=1;d<n;d<<=1)
for(int m=d<<1,i=0;i<n;i+=m)
for(int j=0;j<d;j++){
int x=a[i+j],y=a[i+j+d];
a[i+j]=1LL*(x+y)*rev%MOD,a[i+j+d]=(1LL*(x-y)*rev%MOD+MOD)%MOD;
//xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2; inv
//and:a[i+j]=x-y;
//or :a[i+j+d]=y-x;
}
}

void solve(int a[],int b[],int n){
FWT(a,n);
FWT(b,n);
for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%MOD;
UFWT(a,n);
}

LL A[2222];
int main(){
A[0]=1;
for(int i=1;i<2222;i++) A[i]=A[i-1]*i%MOD;

for(int _=read();_;_--){
n=read(),m=read();
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++) a[i]=1;
for(int i=1;i<=m;i++) b[i]=1;

len = 1024;
solve(a,b,len);

LL ans = 1ll;
for(int i=0;i<len;i++)ans = ans*A[a[i]]%MOD;
printf("%lld\n",ans);
}
return 0;
}