学步园

bitset好神奇==

因为是A*B，而且A,B的元素mod之后只有0、1、2，所以用A[i][k]保存A的第i行数为k的元素的位置，用一个二进制数状态压缩表示，例如A[i][k]=1001，则表示A[i][0]=k,A[i][3]=k

将B转置存储，所以用B[j][k]保存B的第j行数为k的元素的位置。

aij，bij有一者为0时对cij不会有影响，A[i][1]&B[j][1]表示A的行i为1且B的列j为1，可以用count()统计个数，A[i][2]&B[j][2]表示A的行i为2且B的列j为2，因为2*2=4，所以最后要count()*4。只要枚举出1*1,1*2,2*1,2*2几种case即可。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
#include<map>
#include<time.h>
#include<bitset>
using namespace std;
//hdu 4920

const int maxn=810;
int n;
bitset<maxn>A[maxn][3];//<>内为长度，不是int
bitset<maxn>B[maxn][3];
int c[maxn][maxn];
int main()
{
    freopen("input.txt","r",stdin);
    //freopen("data.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    while(scanf("%d",&n)!=EOF)
    {
        long long k=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<3;j++)//之前写成了n，居然T了==
            {
                A[i][j].reset();
                B[i][j].reset();
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%I64d",&k);
                A[i][k%3].set(j);//A的第i行 k%3的数位于第几列，列数用二进制数表示
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%I64d",&k);
                B[j][k%3].set(i);//B的第j行 k%3的数位于第几行，行数用二进制数表示
                //因为是矩阵相乘，所以要将B转置存储
            }
        }
        for(int i=0;i<n;i++)//第i行
        {
            for(int j=0;j<n;j++)//第j列
            {
                c[i][j]=(A[i][1]&B[j][1]).count()+(A[i][1]&B[j][2]).count()*2+(A[i][2]&B[j][1]).count()*2+(A[i][2]&B[j][2]).count()*4;
                c[i][j]%=3;
                if(j==n-1) printf("%d\n",c[i][j]);
                else printf("%d ",c[i][j]);
            }
        }
    }
     return 0;
}