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

Tabris

CSDN数学SPOJ

发布于：2017年7月5日

次浏览

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

——————————————————————————————————————————
题目大意：
给定规则，问你满足这样的矩阵有多少个
规则：

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

本页文档最后更新于：2021年5月16日

CSDN

数学