矩阵乘法分配律+bitset优化——hdu4920

Bertha 。 2021-12-01 16:52 254阅读 0赞

**因为是模3，所以把原矩阵拆成两个01矩阵，然后按分配律拆开分别进行矩阵乘法，行列用bitset来存进行优化即可**

**注意**

**int bitset<int>::count() 函数可以统计bitset里有多少1**

**int bitset<int>::any() 函数可以统计bitset里是否有1 **

/*
    (A+B)*(C+D)=A*C+A*D+B*C+B*D
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 805
    struct Matrix{
        int n; 
        bitset<maxn>r[maxn];//按行表示 
        bitset<maxn>c[maxn];//按列表示 
    }A,B,C,D;
    int E[maxn][maxn],F[maxn][maxn],G[maxn][maxn],H[maxn][maxn];
    int n;
    
    void mul(Matrix A,Matrix B,int res[maxn][maxn]){
        bitset<maxn>tmp;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                tmp=A.r[i]&B.c[j];
                res[i][j]=tmp.count()%3; 
            }
    }
    
    
    int main(){
        while(cin>>n){
            A.n=B.n=C.n=D.n=n;
            for(int i=1;i<=n;i++){
                A.c[i].reset();A.r[i].reset();
                B.c[i].reset();B.r[i].reset();
                C.c[i].reset();C.r[i].reset();
                D.c[i].reset();D.r[i].reset(); 
            } 
             
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++){
                    int x;
                    scanf("%d",&x);
                    x%=3;
                    if(x>=1){
                        A.r[i][j]=1;
                        A.c[j][i]=1;
                    }
                    if(x==2){
                        B.r[i][j]=1;
                        B.c[j][i]=1;
                    }
                }
            
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++){
                    int x;
                    scanf("%d",&x);
                    x%=3;
                    if(x>=1){
                        C.r[i][j]=1;
                        C.c[j][i]=1;
                    }
                    if(x==2){
                        D.r[i][j]=1;
                        D.c[j][i]=1;
                    }
                }
            mul(A,C,E);mul(A,D,F);
            mul(B,C,G);mul(B,D,H);
            
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    int ans=E[i][j]+F[i][j]+G[i][j]+H[i][j];
                    if(j!=1)
                        printf(" ");
                    printf("%d",ans%3);
                }
                puts("");
            }    
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11182183.html