[原创]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

Each element in the matrix is distinct and lies in the range of 1<=A[i][j]<=(N*M)
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

SAMPLE OUTPUT

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]$

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

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

所以问题就是找 $(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]= \displaystyle \sum_{x=i\ xor\ j}a_i \times b_j$

上式即是期望结果,

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

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

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

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;
}