先把两个矩阵全都mod3。
S[i][j][k]表示第i(0/1)个矩阵的行/列的第k位是不是j(1/2)。
然后如果某两个矩乘对应位上为1、1，乘出来是1；
1、2：2；
2、1：2；
2、2：1。
然后分这四种情况把bitset and 起来，然后用count()数一下个数，计算下对答案矩阵该位置的贡献即可。
#include<cstdio>
#include<bitset>
using namespace std;
#define N 801
int n,x;
bitset<N>S[2][2][N];
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;++i)
{
S[0][0][i].reset();
S[0][1][i].reset();
S[1][0][i].reset();
S[1][1][i].reset();
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&x);
int op=x%3-1;
if(op!=-1) S[0][op][i][j]=1;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&x);
int op=x%3-1;
if(op!=-1) S[1][op][j][i]=1;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
printf("%d",((S[0][0][i]&S[1][0][j]).count()+
((S[0][0][i]&S[1][1][j]).count()<<1)+
((S[0][1][i]&S[1][0][j]).count()<<1)+
(S[0][1][i]&S[1][1][j]).count())%3);
putchar(j==n?‘\n‘:‘ ‘);
}
}
return 0;
}
【bitset】hdu4920 Matrix multiplication
原文：http://www.cnblogs.com/autsky-jadek/p/4311907.html